可见的点

欧拉函数 T2 https://vjudge.csgrandeur.cn/problem/ZOJ-2777#author=chen_zhe_

统计在矩形区域(0,0)到(n,n)中，所有非原点到原点的线段中所有不经过其他点的线段数。
栗如：(4,2)到(0,0)的线段中，经过了(2,1)，就不在被统计的范围之内。

输入格式

多组数据（不超过1000组）
第一行：c表示数据组数
后面c行：每行一个n，含义见题目描述，n<=1000

输出格式

对于第i组数据，查询的是n，在一行里输出：（空格分隔）

• i
• n
• 你的答案

输入样例

4
2
4
5
231

输出样例

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

思路

可以看作在原点有一个光源， 求它能照到的点个数。

对于任意一点 $x_0,y_0$ 当它能被照到，说明在直线 $y=k_{0}x$ 中往下不存在另一个点。

即 $y=\frac{y_0}{x_0}x$， 因为点都是整数点， 那么当 $gcd(y_0,x_0)=d>1$时， 存在一个数对 $(\frac{x_0}{d},\frac{y_0}{d})$ 同样在这条直线上并且位置更偏原点， 这时点 $(x_0,y_0)$ 就会被挡住。

那么就有一个结论， 当 $x_0,y_0$ 互质时， 就可以被照到。

问题转化为在 $0\le x,y\le N$ 中求 $x,y$ 互质的数对个数， 且 $(1,2)$ 和 $(2,1)$ 算两个。

首先可以发现 $1,2$ 和 $2,1$ 都互质， 有对称性， 故只需要求 $y=x$ 直线下的点方案数， 然后乘2就是总的方案数。

此时我们如果枚举 $x$, 显然 $1\le y<x$ ， 也就是说， 对于每个 $x_i$， 满足条件的数对数量和 $[1,x_i)$ 内与 $x_i$ 互质的个数。

因此直接欧拉筛掉 1到1000 每个数的互质个数， 然后枚举求和并乘以2就是最终答案。即 $(\phi (1)+\phi (2)+\cdots +\phi (n))\times 2+1$， 加1是因为在 $y=x$ 上也有一个点。

代码

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e3 + 10;
int phi[N], primes[N], cnt;
int T;
 
bool st[N];
 
void init()
{
    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[primes[j] * i] = true;
            if(i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
}
 
void solve() {
    int n;
    cin >> n;
    int res = 1;
    for(int i = 1; i <= n; i++) res += phi[i] * 2;
    cout << T << " " << n << " " << res << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int m;
    cin >> m;
    for(T = 1; T <= m; T++) solve();
    return 0;
}