Description：

一个 $R\times C$ 的矩形，沿着一个对角线射箭，问有多少种 $(R,C)$ 使得箭恰好经过了 $N$ 个矩形。

当 $N=4$ 时：

$1\leqslant n\leqslant 10^6$

Solution：

首先发现当 $\gcd(R,C)=1$ 时，路径不会经过任意一个点，那么每穿过一条边就会增加 $1$ ，于是答案是 $R+C-1$ ，扩展一下这个结论会发现经过的格子数是 $R+C-\gcd(R,C)$ ，于是我们就要统计 $N=R+C-\gcd(R,C)$ 的解的个数，发现他们必须都是 $\gcd(R,C)$ 的倍数，所以 $\frac N{\gcd(R,C)}=r+c-1$ ，设 $n=\frac N{\gcd(R,C)}$ ，那么我们就要统计 $n=r+c-1$ 其中 $\gcd(r,n+1)=1,\gcd(c,n+1)=1$ 的个数，因为如果 $\gcd(r,n+1)\ne 1$ ，那么一定有 $\gcd(r,c)\ne1$ ，所以说这个值就是 $\varphi(n+1)$ ，因为 $r$ 和 $c$ 是成对出现的，最后的答案就是： $$ ans=\frac{\begin{align}\sum_{i|n}\varphi(n+1)+1\end{align}}2 $$ 因为 $(N,N)$ 只能统计一次。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int phi[MAXN];

bool isprime[MAXN];

int prime[MAXN],tot = 0;

int main()

{

	scanf("%d",&n);

	for(int i = 2;i <= n + 1;++i)isprime[i] = true;

	for(int i = 2;i <= n + 1;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			phi[i] = i - 1;

		}

		for(int j = 1;j <= tot && i * prime[j] <= n + 1;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)

			{

				phi[i * prime[j]] = phi[i] * prime[j];

				break;

			}

			else

			{

				phi[i * prime[j]] = phi[i] * (prime[j] - 1);

			}

		}

	}

	long long ans = 0;

	for(int i = 1;i <= n;++i)

	{

		if(n % i == 0)

		{

			ans += phi[i + 1];

		}

	}

	cout << (ans + 1) / 2 << endl;

	return 0;

}