p4388付公主的矩形
线每次穿过一个格子都会经过一条边
就可以得到要走r+c-1，但是x/y=r/c处经两个边但只穿了一个格子所以
穿过格子数N=R+C-gcd（R,C）
我们现在知道N，求满足该式的解的个数
此时r和c互质，n是N的因数
即gcd（r，c）=1
gcd（r，c）=gcd（r+c，c）=gcd（n+1，c）=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;
} 
格力公司福利 356人发布
