Jzoj3927 可见点数

ZPS经过长期的努力争取，终于成为了0901班的领操员，他要带领0901班参加广播操比赛。现在0901班的队伍可以看作是一个n*n的点阵，每个人都站在格点上。现在作为领操员的ZPS站(0,0)点，他想知道如果0901班的队伍站齐了，他能看到多少个人的脸（假设每个人的身高相同，体积相同）

这个题很容易发现，若一个点(x,y)可以被看到，那么gcd(x,y)=1，否则一定会被(x/gcd,y/gcd)挡住

这样的话，我们问题变成了求点对(x,y)使得gcd(x,y)=1，按道理来说应该要用莫比乌斯反演，但是这道题是方阵而不是矩阵所以答案就是2(Σφ(i) (1<=i<=n))+1

至于如何求φ，可以用线性筛法，和素数筛法一样

#include<stdio.h>
bool vis[1000010];
int w[1000010],t=0,n,phi[1000010];
void Gphi(){
	phi[1]=1;
	for(int i=2;i<=n;++i){
		if(!vis[i]) w[t++]=i,phi[i]=i-1;
		for(int j=0;j<t&&i*w[j]<=n;++j){
			vis[i*w[j]]=1;
			if(i%w[j]==0){
				phi[i*w[j]]=phi[i]*w[j];
				break;
			}
			else phi[i*w[j]]=phi[i]*(w[j]-1);
		}
	}
}
int main(){
	scanf("%d",&n);n--; Gphi();
	if(n==0){ return puts("0")&0; }
	long long ans=0;
	for(int i=1;i<=n;++i) ans+=phi[i];
	printf("%lld
",ans*2+1);
}