P2158题解
[SDOI2008] 仪仗队
题目描述
作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 $N \times N$ 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。
现在，C 君希望你告诉他队伍整齐时能看到的学生人数。
题解
首先考虑从C君引出的一条直线上只会有一个点产生贡献，由此想到一次函数。
考虑以C君为原点建系，显然只有横纵坐标互质的点会产生贡献，又因为横纵坐标对称，所以只需要算出1n-1的欧拉函数之和乘2即可，特判(1,1)(注意这里是1n-1的和，部分题解给出的解释是因为算的行列是1~n-1，但其实只是碰巧相等而已，实质是多出的，和少的部分相等)。
最后注意一下欧拉函数和埃氏筛的求法。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+100;
int n,p[N],ans;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
p[i]=i;
for(int i=2;i<=n;i++)
if(p[i]==i)
for(int j=i;j<=n;j+=i)
p[j]-=p[j]/i;
for(int i=1;i<=n-1;i++)
ans+=p[i];
ans*=2;
if(n!=1)
ans+=1;
cout<<ans;
return 0;
}