POJ3090Visible Lattice Points

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

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

 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  } 

 

上一篇:李宏毅2021春机器学习课程笔记——生成对抗模型(一)


下一篇:AI框架中图层IR的分析