Lattice Points-欧拉函数

A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For example, the point (4, 2) is not visible since the line from the origin passes through (2, 1). The figure below shows the points (x, y) with 0 ≤ x, y ≤ 5 with lines from the origin to the visible points.
Write a program which, given a value for the size, N, computes the number of visible points (x, y) with 0 ≤ x, y ≤ N.
Input
The first line of input contains a single integer C (1 ≤ C ≤ 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing a single integer N (1 ≤ N ≤ 1000), which is the size.
Output
For each dataset, there is to be one line of output consisting of: the dataset number starting at 1, a single space, the size, a single space and the number of visible points for that size.
Sample Input
4
2
4
5
231
Sample Output
1 2 5
2 4 13
3 5 21
4 231 32549

思路
题意：给你一个nxn的方阵，从原点去看别的点，与原点连线斜率相同的点只能看见一个，比如连上(4,2)之后就看不到(2,1);也就是求方阵中有多少不同的斜率
因为直线在方阵中上三角下三角都是对称的，所以只需要求下三角中的斜率数，再用得到的结果x2+1(1代表斜率为1的直线)
------------------------举例分析------------------------
1x1方阵中，只有1/1的斜率
2x2方阵中，有1/2,2/2(1*1中已存在)的斜率–新增1个
3x3方阵中，有1/3，2/3，3/3(已存在)的斜率–新增2个
4x4方阵中，有1/4，2/4(已存在)，3/4，4/4(已存在)–新增2个
5x5方阵中，有1/5，2/5，3/5，4/5–新增四个
…
每个nxn方阵中新增的斜率数其实就是与小于n的与n互质的数的个数，这里就用到了欧拉函数

#include <bits/stdc++.h>
using namespace std;
int euler[1005];
void euler_phi(int n){
    for(int i=1;i<=n;i++)
		euler[i]=i;	//初始化默认1~i都互质i
    for(int i=2;i<=n;i++)
		if(euler[i]==i)//euler[i]==i表示i没有被前面的数更新,即i是质数,然后就用它去更新他的所有倍数
			for(int j=i;j<=n;j+=i)//for example:第一轮2,更新2,4,6,8,10的欧拉值,第二轮3,就更新3,6,9的欧拉值,第三轮4不用更新
				euler[j]=euler[j]/i*(i-1);
}
int main(){
	int nTest,n,ans,cnt=0;
	cin >> nTest;
	while(nTest--)
	{
		cnt++;
		ans=0;
		cin >> n;
		euler_phi(n);
		for(int i=1;i<=n;i++)
			ans+=euler[i];
		cout << cnt << " " << n << " "<< ans*2+1 << endl;
	}
}