3927. 【NOIP2014模拟11.6】可见点数
Description
ZPS经过长期的努力争取，终于成为了0901班的领操员，他要带领0901班参加广播操比赛。现在0901班的队伍可以看作是一个n*n的点阵，每个人都站在格点上。现在作为领操员的ZPS站(0,0)点，他想知道如果0901班的队伍站齐了，他能看到多少个人的脸（假设每个人的身高相同，体积相同）。
Input
一个正整数n。
Output
ZPS能看到多少个人的脸（当然他是看不到自己的脸的）。
分析：这题很显然两个坐标互质就可以看得到，用欧拉函数求就行了。
代码
#include <cstdio>
#define maxn 100000
using namespace std;
int f[maxn];
int main()
{
int n;
scanf(
"%d",&n);
for (
int i=
1;i<=n;i++)
f[i]=i;
for (
int i=
2;i<=n;i++)
if (i%
2==
0) f[i]/=
2;
else if (f[i]==i)
{
for (
int j=i;j<=n;j+=i)
f[j]=f[j]/i*(i-
1);
}
long long ans=
0;
for (
int i=
1;i<n;i++)
ans+=f[i];
if (n==
1)
printf(
"0");
else printf(
"%lld",ans*
2+
1);
}
