莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 求解有多少种斜率，即求有多少对数对 (x,y) 互质
2. 数对关于直线 y = x 对称，在直线 y = x 下方，与 n 互质的个数为 phi[n]

// 1.当 i 是质数的时候，1 ～ i - 1 都与 i 互质，故 phi[i] = i - 1
// 2.当 i % primes[j] == 0 时，primes[j] 是 i 的最小质因子
//   故 i 的所有质因子都与 primes[j] * i 的质因子相同
//   而 primes[j] * i 的欧拉函数比i还多了一个 primes[j]
//   所以 phi[primes[j] * i] = phi[i] * primes[j]
// 3.当 i % primes[j] != 0 时，primes[j] 小于 i 的最小质因子
//   故 primes[j] * i 比 i 还多一个质因子 primes[j]
//   所以 primes[j] * i 的欧拉函数比 i 多了一个 primes[j](1 - 1 / primes[j]) = primes[j] - 1
//   故 phi[primes[j] * i] = phi[i] * (primes[j] - 1)

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n;
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]<=n/i;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);
        }
    }
}

int main()
{
    init(N-1);

    int T;
    cin>>T;

    for(int i=1;i<=T;i++)
    {
        cin>>n;

        int res=1;
        for(int i=1;i<=n;i++) res+=phi[i]*2; // 关于直线 y = x 对称

        cout<<i<<' '<<n<<' '<<res<<endl;
    }

    return 0;
}