传送门
题意：
思路：直接上杜教筛。
知道怎么推导就很简单了，注意预处理的范围。
然后我因为预处理范围不对被zxyoi教育了（ldx你这个傻×两倍常数活该被卡TLE） 喜闻乐见
代码：
#include<bits/stdc++.h>
#define ri register int
using 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<int,int>mpa;
map<int,ll>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<=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<=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<<Sieve::Phi(n)<<' '<<Sieve::Mu(n)<<'\n';
return 0;
}