除左下角三个点之外, 可以发现所有能被看到的点$latex (x,y)$都满足$latex gcd(x,y)=1$.
由于正方形对称性, 我们可以考虑对角线右下方的一半: 所有满足$latex 2<=x<y<=N, gcd(x,y)=1$的点, 即对于每个$latex 2<=y<=N$, 求$latex \varphi (y)$.
答案为$latex 3+2*\sum_{i=2}^{N}\varphi (i)$.
#include<cstdio>
#define re register
#define in inline
#define int long long
int n,phi[40001];
signed main()
{
scanf("%lld",&n);
if(n==1) {printf("0\n");return 0;}
for(re int i=1;i<=n;++i) phi[i]=i;
for(re int i=2;i<=n;++i)
{
if(phi[i]==i){
for(re int j=i;j<=n;j+=i)
phi[j]=phi[j]/i*(i-1);
}
}
int ans=0;
for(re int i=2;i<=n-1;++i) ans+=phi[i];//注意编号是从0开始的,循环到n-1即可
printf("%lld\n",ans*2+3);
return 0;
}
最新评论