p4388付公主的矩形

线每次穿过一个格子都会经过一条边

就可以得到要走r+c-1，但是x/y=r/c处经两个边但只穿了一个格子所以

穿过格子数N=R+C-gcd（R,C）

我们现在知道N，求满足该式的解的个数

$应满足式:\frac{N}{gcd}=\frac{R}{gcd}+\frac{C}{gcd}-1$ R和C是肯定可以被gcd（R,C）整除，所以等式右边可以被gcd整除，所以左边——N可以被gcd整除

$（简化）n=r+c-1$

此时r和c互质，n是N的因数

即gcd（r，c）=1

gcd（r，c）=gcd（r+c，c）=gcd（n+1，c）=1

求 $\sum_{n|N}^{}{\varphi（n+1）}$

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+4;

int n,ans;
int prime[N],phi[N],cnt;
bool st[N];

int main(int argc, char** argv) {
	cin>>n; 
	for(int i=2;i<=n+1;i++){
		if(!st[i]){
			prime[cnt++]=i; phi[i]=i-1;
		}
		if(n%(i-1)==0) ans+=phi[i];//因为n是不变的所以不能用n的因数分解的方式写(每次要n/i) 
		for(int j=0;prime[j]<=(n+1)/i;j++){
			st[i*prime[j]]=true;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j]; break;
			}else{
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
		}
	}	
	cout<<(ans+1)/2<<endl;
	return 0;
}