可见的点

在一个平面直角坐标系的第一象限内，如果一个点(x,y)与原点（0,0）的连线中没有通过其他任何点，则称该点在原点处是可见的。

例如，点(4,2)就是不可见的，因为它与原点的连线会通过点(2,1)。

部分可见点与原点的连线如下图所示：

编写一个程序，计算给定整数N的情况下，满足0≤x，y≤N的可见点（x，y）的数量（可见点不包括原点）。

输入格式

第一行包含整数C，表示共有C组测试数据。

每组测试数据占一行，包含一个整数N。

输出格式

每组测试数据的输出占据一行。

应包括：测试数据的编号（从1开始），该组测试数据对应的N以及可见点的数量。

同行数据之间用空格隔开。

数据范围

1≤N,C≤1000

输入样例：

4
2
4
5
231

输出样例：

1 2 5
2 4 13
3 5 21
4 231 32549

思路：判断有多少个可见的点，其实就是看(0,0)与(x,y)有多少条不重复的斜率，$k = (y_{2}-y_{1})/(x_{2}-x_{1})$,分子范围是[0,N],分母的范围也是[0,N]，然后我们需要对他去重，把可约分的分数去掉，留下来的都是不可约的分数，所以到这里，我们只需要遍历分母[0,N]，分母为0为竖直单独+1，之后遍历[1,N]的欧拉值求和(可用前缀和优化)，因为分子分母可以颠倒仍然不可以约，所以需要再乘以2.

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int E[maxn];
int sum[maxn];
int T,N;
void init()
{
    E[1] = 1;
    for(int i=2;i<maxn;i++){
        if(!E[i])
            for(int j=i;j<maxn;j+=i){
                if(!E[j]) E[j]=j;
                E[j] = E[j]/i*(i-1);
            }
    }
    for(int i = 1;i<maxn;i++) sum[i] = E[i]+sum[i-1];
}
int main(){
    init();
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%d",&N);
        int ans = sum[N]*2+1;
        printf("%d %d %d\n",++kase,N,ans);
    }

    return 0;
}