可见的点

原题链接：201. 可见的点 - AcWing题库

题意：从原点可以直接到达（不经过其他点）的点为可见点，给定（x,y)的范围N，求一共有多少可见点

思路

可见点不能经过其他点

即二者不能有公因子，即互质

假设一个点(y)固定，那么另一个点的取值的个数就是从0到y的与y互质的数的个数

欧拉函数

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
typedef long long LL;
 
const int N = 1e4 + 10;
 
LL p[N];
int n;
 
int get_euler(int n)
{
    LL ans = n;
    for(int i = 2; i <= n / i; i ++)
    {
        if(n % i == 0)
        {
            ans = ans / i * (i - 1);
            while(n % i == 0)
                n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    
    return ans;
}
 
int main()
{
    cin >> n;
    for(int i = 1; i <= 1000; i ++)
    {
        p[i] = get_euler(i);
        p[i] += p[i-1];
    }
    //cout << p[1] << endl;
    for(int i = 1; i <= n; i ++)
    {
        int N;
        cin >> N;
        cout << i << ' ' << N << ' ' << 2 * p[N] + 1 << endl;
    }
    
    return 0;
}