思路

没学过数论的同学估计一开始是不会想到欧拉函数的。
那么我们怎么去联想到这东西呢。
这道题，我们只需要计算y>x的点（上三角），然后答案就是2*ans+1了。(上三角+下三角+斜率为1的点)
我们现在通过找规律来看看n不同时斜率的一个情况(y/x):
n=1,ans=0;
n=2,ans=1,k=1/2
n=3,ans=2,k=1/3,2/3
n=4,ans=2,k=1/4,3/4（k=2/4已经被数过了）
...
凡是分子分母能约分的，前面都已经出现过，所以我们每次添加的数，分子分母都是互质的，
那么我们可以把问题转化为对于一个数n,求小于n且与n互质的数的个数，即求欧拉函数。
这样，我们就把二者结合起来了。

代码

#include<stdio.h>
const int maxn=10005;
bool isn_pri[maxn];
int phi[maxn],pri[maxn];
int n,ans,T,cnt;

void get(int x){
    phi[1]=1;
    for(int i=2;i<=x;i++){
        if(!isn_pri[i]){
            pri[++cnt]=i; //素数增加 
            phi[i]=i-1; //素数直接i-1 
        }
        for(int j=1;j<=cnt&&i*pri[j]<=x;j++){
            isn_pri[i*pri[j]]=1; //标记为合数 
            if(i%pri[j]==0){ //i可以分解 
                phi[i*pri[j]]=phi[i]*pri[j]; //利用积性函数的性质 
                break;
            }else{
                phi[i*pri[j]]=phi[i]*(pri[j]-1);  //要积性再减去phi[i]个数，因为和pri[j]不互质 
            }
        }
        ans+=phi[i];
    }    
}

signed main(){
    get(maxn-5); 
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        scanf("%d",&n);
        ans=0;
        for(int i=1;i<=n;i++) ans+=phi[i]; //只计算了下三角 
        printf("%d %d %d\n",t,n,ans*2+1);   //下三角+上三角+斜率为1的点 
    }
    return 0;
}