题意：问从(0,0)到(x,y)(0≤x, y≤N)的线段没有与其他整数点相交的点数。
解法：只有 gcd(x,y)=1 时才满足条件，问 N 以前所有的合法点的和，就发现和上一题—— 【poj 2478】Farey Sequence（数论--欧拉函数 找规律求前缀和） 求 x/y，gcd(x,y)=1 且 x<y 很像。
而由于这里 x可等于或大于y，于是就求 欧拉函数的前缀和*2+边缘2个点+对角线1个点。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6 #define N 1000
7 typedef long long LL;
8
9 int pr=0;
10 int prim[N+10],v[N+10],phi[N+10];
11 LL sphi[N+10];
12
13 void get_prime()
14 {
15 memset(v,0,sizeof(v));
16 for (int i=2;i<=N;i++)
17 {
18 if (!v[i]) prim[++pr]=i, phi[i]=i-1;
19 for (int j=1;j<=pr && i*prim[j]<=N;j++)
20 {
21 v[i*prim[j]]=1;
22 if (i%prim[j]!=0) phi[i*prim[j]]=phi[i]*phi[prim[j]];
23 else {phi[i*prim[j]]=phi[i]*prim[j]; break;}
24 }
25 }
26 sphi[1]=0;
27 for (int i=2;i<=N;i++) sphi[i]=sphi[i-1]+phi[i];
28 }
29 int main()
30 {
31 get_prime();
32 int T,n;
33 scanf("%d",&T);
34 for (int kase=1;kase<=T;kase++)
35 {
36 scanf("%d",&n);
37 printf("%d %d %lld\n",kase,n,2*sphi[n]+3);
38 }
39 return 0;
40 }