题目
在一个平面直角坐标系的第一象限内，如果一个点(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
思路
题目要求的其实就是所有直线上第一个进过的点的数量，可以发现一条直线上第一个点的坐标x，y是互质的，所以就只要求有多少个互质的点即可，即对于每一个x，求一下有多少个y和他互质，又由于整个图是关于y=x对称的，所以就可以只求对于每一个x有多少个小于x的y和x互质，数量求和再乘以2即可
代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std
;
const int N
= 1010;
int primes
[N
], cnt
;
bool st
[N
];
int phi
[N
];
void init(int n
)
{
phi
[1] = 1;
for (int i
= 2; i
<= n
; i
++ )
{
if (!st
[i
])
{
primes
[cnt
++ ] = i
;
phi
[i
] = i
- 1;
}
for (int j
= 0; primes
[j
] * i
<= n
; j
++ )
{
st
[i
* primes
[j
]] = true;
if (i
% primes
[j
] == 0)
{
phi
[i
* primes
[j
]] = phi
[i
] * primes
[j
];
break;
}
phi
[i
* primes
[j
]] = phi
[i
] * (primes
[j
] - 1);
}
}
}
int main()
{
init(N
- 1);
int n
, m
;
cin
>> m
;
for (int T
= 1; T
<= m
; T
++ )
{
cin
>> n
;
int res
= 1;
for (int i
= 1; i
<= n
; i
++ ) res
+= phi
[i
] * 2;
cout
<< T
<< ' ' << n
<< ' ' << res
<< endl
;
}
return 0;
}
