Visible Lattice Points 欧拉函数应用
/*根据题意。如果该点是不可见的。则必定经过整数点。也就是非互质。相反，如果是可见的，那么必定是互质的。则题目转为求1-n内的互质点对数。即为求1-ai(i:1-n)内的欧拉函数值。可现在1-n的范围内用递推打表生成欧拉函数值。*/#include <stdio.h>const int maxn=1001;int phi[maxn];void get_phi()//获取1-maxn范围内的欧拉函数表{ for(int i=1;i<=maxn;i++) phi[i]=i; for(int i=2;i<=maxn;i+=2) phi[i]/=2; for(int i=3;i<=maxn;i+=2) if(phi[i]==i) { for(int j=i;j<=maxn;j+=i) phi[j]=phi[j]/i*(i-1); } for(int i=2;i<maxn+1;i++) phi[i]+=phi[i-1];//预处理出前n项内互素的对数}int main(){ int t,n; scanf("%d",&t); get_phi(); for(int i=1;i<=t;i++) { scanf("%d",&n); printf("%d %d %d\n",i,n,phi[n]*2+1); } return 0;}