欧拉函数:
在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目

$N = p_{1}^{\alpha_{1}} * p_{2}^{\alpha_{2}} … p_{k}^{\alpha_{k}}$
$\phi(N) = N*(1-\frac{1}{p1}) * (1-\frac{1}{p2}) … * (1-\frac{1}{pk})$

$p_{j}$是$i$的最小质因子
$i = p_{1}^{\alpha_{1}} * p_{2}^{\alpha_{2}} … p_{k}^{\alpha_{k}}$
目标求 $\phi(i * p_{j})$
$\phi(i) = i*(1-\frac{1}{p1}) * (1-\frac{1}{p2}) … * (1-\frac{1}{pk})$
以$p_{1}$为例 只会改变$p_{1}$的次数
$i * p_{1} = p_{1}^{\alpha_{1}+1} * p_{2}^{\alpha_{2}} … p_{k}^{\alpha_{k}}$

则$$ \begin{align} 情况1 i mod p_{j} &= 0 \\\\ \phi(i * p_{j} ) &= i * p_{j}*(1-\frac{1}{p1}) * (1-\frac{1}{p2}) … * (1-\frac{1}{pk}) \\\\ &= \phi(i) * p_{j} \\\\ 情况2 i mod p_{j} &≠ 0(此时p_{j}不在i的质因子展开表达式里) \\\\ i * p_{j} &= p_{j} * p_{1}^{\alpha_{1}} * p_{2}^{\alpha_{2}} … p_{k}^{\alpha_{k}} \\\\ \phi(i * p_{j} ) &= i * p_{j} * (1-\frac{1}{pj}) * (1-\frac{1}{p1}) * (1-\frac{1}{p2}) … * (1-\frac{1}{pk}) \\\\ &= i * (p_{j}-1) * (1-\frac{1}{p1}) * (1-\frac{1}{p2}) … * (1-\frac{1}{pk}) \\\\ &= \phi(i) * (p_{j}-1) \end{align} $$

本题
$x,y \in [0,N]$
对于$x_{0},y_{0}$要被照到
在$y = kx$直线上 没有在$x_{0},y_{0}$左下方且同样在直线上的点
$k = \frac{y0}{x0}$
$y = \frac{y0}{x0} * x \iff x_{0}和y_{0}互质$

证明:
1 假设$x_{0}和y_{0}$不互质
则此时有公约数d使得
$\frac{x_{0}}{d}和\frac{y_{0}}{d}$在$x_{0}和y_{0}$左下方
=>被照到的点的x和y都是互质的
=>问题转化为在[0,N]找所有的互质对(x,y)数量

以$y=x$为分界线
利用左上和右下对称分布,左上互质对数量==右下互质对数量
=>只用看右下互质对数量

则右下所有横坐标对应的互质数个数$=\sum_{i=1}^{N} \phi(i)$

右下+对称的左上$=2*\sum_{i=1}^{N} \phi(i)$

右下+左上+中间点$=1 + 2*\sum_{i=1}^{N} \phi(i) $

#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;
            //情况1 primes[j]是i的最小质因子
            if(i%primes[j]==0)
            {
                phi[i*primes[j]] = phi[i]*primes[j];
                break;
            }
            //情况2
            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;
}