题解 P2158 【[SDOI2008]仪仗队】

· · 题解

其实这道题一开始我已经接近正解了，就是他能看到的点的横纵坐标都是互质的。但我不知道怎么求一个数与其互质的个数，尝试着用组合数学的方式去做，结果才得了9分。看了一下题解顿时茅塞顿开。

都这么明显了，一个裸的欧拉函数啊！具体求欧拉函数请自行查阅资料，这里不再赘述。 还有要注意，点(1,2)(2,1)(2,2)也是能看见的，所以初值为3；欧拉函数只对于有序数对，所以在网格中还要*2.

#include<cstdio>
#include<algorithm>
using namespace std;
int n,num;
long long ans=3,sum,e[40012];
int main()
{
    scanf("%d",&n);
    for (int i=1; i<=n; i++) e[i]=i;
    for (int i=2; i<=n; i++)
        if (e[i]==i)//质数
        {
            for (int j=i; j<=n; j+=i)//等同于筛法
            e[j]=e[j]/i*(i-1); //e[n]=n/p1*(p1-1)/p2……/pm*(pm-1) p为n的质因子
        }
    n--;
    for (int i=2; i<=n; i++) ans+=e[i]*2;
    printf("%lld\n",ans);
    return 0;
}