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  }