电视家日本付费分享码/百度优化关键词

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

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

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

3090_1.png

编写一个程序，计算给定整数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

思路：
题目可以转换成，能寻找出多少$k=(y2-y1)/(x2-x1)$
其中y2,x2均为非负整数，且x1 = y1 = 0。
且易得y2和x2一定是没有公约数的，否则将其约去公约数后的点一定在其左下被提前看到。
那么gcd(x2,y2) = 0。
需要特殊考虑的是(1,0),(0,1),(1,1)这三个点。
不妨设$y2>x2$。所以本题转换成了求2~n内欧拉函数的和，同时这个和要乘以2,再加上一开始的3个点。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 1005;
int v[maxn],phi[maxn],prime[maxn];
int sum[maxn];void euler()
{int cnt = 0;for(int i = 2;i <= 1000;i++){if(v[i] == 0){v[i] = i;phi[i] = i - 1;prime[++cnt] = i;}for(int j = 1;j <= cnt && prime[j] * i < maxn;j++){v[i * prime[j]] = prime[j];phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);if(i % prime[j] == 0)break;}}
}int main()
{euler();int T;scanf("%d",&T);for(int i = 1;i <= 1000;i++){sum[i] = sum[i - 1] + phi[i];}int kase = 0;while(T--){int n;scanf("%d",&n);printf("%d %d %d\n",++kase,n,sum[n] * 2 + 3);}return 0;
}