题意：

---

思路：直接上杜教筛。

知道怎么推导就很简单了，注意预处理的范围。

然后我因为预处理范围不对被zxyoi教育了（ldx你这个傻×两倍常数活该被卡TLE） 喜闻乐见

代码：

#include
    
     #define ri register intusing namespace std;const int N=7500005,lim=7500000;typedef long long ll;namespace Sieve{
    	int pri[N],tot=0,mu[N];	ll phi[N];	bool vis[N];	map
     
      mpa;	map
      
       mpb;	inline void init(){
    		vis[1]=phi[1]=mu[1]=1;		for(ri i=2;i<=lim;++i){
    			if(!vis[i])pri[++tot]=i,phi[i]=i-1,mu[i]=-1;			for(ri j=1;j<=tot&&i*pri[j]<=lim;++j){
    				vis[i*pri[j]]=1;				if(i==i/pri[j]*pri[j]){
    					phi[i*pri[j]]=pri[j]*phi[i],mu[i*pri[j]]=0;					break;				}				phi[i*pri[j]]=(pri[j]-1)*phi[i],mu[i*pri[j]]=-mu[i];			}		}		for(ri i=2;i<=lim;++i)phi[i]+=phi[i-1],mu[i]+=mu[i-1];	}	inline int Mu(const int&x){
    		if(x<=lim)return mu[x];		if(mpa[x])return mpa[x];		int ret=0;		for(ri l=2,r;r
       
        <=x;l=r+1)r=x/(x/l),ret+=Mu(x/l)*(r-l+1);		return mpa[x]=1-ret;	}	inline ll Phi(const int&x){
    		if(x<=lim)return phi[x];		if(mpb[x])return mpb[x];		ll ret=0;		for(ri l=2,r;r
        
         <=x;l=r+1)r=x/(x/l),ret+=Phi(x/l)*(r-l+1);		return mpb[x]=(ll)x*((ll)x+1)/2-ret;	}}int main(){
    	freopen("lx.in","r",stdin);	Sieve::init();	int tt,n;	scanf("%d",&tt);	while(tt--)scanf("%d",&n),cout<
         
          <<' '<
          
           <<'\n'; return 0;}