POJ3090Visible Lattice Points

http://poj.org/problem?id=3090

对于此题，观测点的数目，从小规模开始观察，可以得到每一个点，由一根无限长的绳子，绕着原点旋转，得到的第一个点。换另外一个思路，每一个观察到的点，都是子矩阵的一个边界点，也就是说枚举每一个子矩阵的点即可，而对于重合的点，则是已经出现的点，也就是可以约分的点，斜率可以看出。那么也就是欧拉函数，通过线性筛欧拉函数，然后对于每一个询问，直接计算欧拉函数和即可。因为是对称的，所以只要求一半，后面再乘2+加上k=1的那一个就可以了

 1 #include<iostream>

 2 #include<stdio.h>

 3 #include<cstring>

 4 #include<math.h>

 5 #include<algorithm>

 6 using namespace std;

 7 typedef long long ll;

 8 const ll N=1e3+520;

 9 bool vis[N];

10 ll phi[N],p[N],cnt;

11 ll n,ans,t;

12 void euler()

13 {

14     phi[1]=1;

15     for(int i=2;i<=N;i++)

16     {

17         if(!vis[i]) p[cnt++]=i,phi[i]=i-1;

18         for(int j=0;p[j]<=N/i;j++)

19         {

20             vis[p[j]*i]=1;

21             if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}

22             phi[i*p[j]]=phi[i]*(p[j]-1);

23         }

24     }

25 }

26 int main()

27 {

28     euler();

29     scanf("%lld",&t);

30     for(int i=1;i<=t;i++)

31     {

32         scanf("%lld",&n);

33         ans=0;

34         for(int j=1;j<=n;j++) ans+=phi[j];

35         printf("%d %lld %lld\n",i,n,ans*2+1);

36     }

37     return 0;

38  }

巴特西

POJ3090Visible Lattice Points

最新文章

热门文章