[SDOI2008]仪仗队[欧拉函数]

题面

除左下角三个点之外, 可以发现所有能被看到的点$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;
}