链接:
https://www.acwing.com/problem/content/description/203/
题意:
在一个平面直角坐标系的第一象限内，如果一个点(x,y)与原点（0,0）的连线中没有通过其他任何点，则称该点在原点处是可见的。
例如，点(4,2)就是不可见的，因为它与原点的连线会通过点(2,1)。
部分可见点与原点的连线如下图所示：
编写一个程序，计算给定整数N的情况下，满足0≤x，y≤N的可见点（x，y）的数量（可见点不包括原点）。
思路:
考虑当gcd(x, y) != 1时, 坐标(x/gcd(x, y), y/gcd(x, y))和坐标(x, y),位于一条直线上.
所以只有gcd(x, y)为1的点可以看得到. 打个表, 再在答案上加1即可.考虑(1, 1)
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL Cnt[1010];
int n;
int Euler(int x)
{
int res = x;
for (int i = 2;i <= x;i++)
{
if (x%i == 0)
{
while (x % i == 0)
x /= i;
res = res/i*(i - 1);
}
}
if (x > 1)
res = res/x*(x-1);
return res;
}
int main()
{
for (int i = 1;i <= 1000;i++)
Cnt[i] = Cnt[i-1]+Euler(i)*2;
int t, cnt = 0;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
printf("%d %d %lld\n", ++cnt, n, Cnt[n]+1);
}
return 0;
}