题目
思路
对于第一个询问,令 \(g=I,h=id\),则满足 \(h=\varphi*g\),带入得
\[\text{Ans}_1(n)=\frac{n(n+1)}{2}-\sum_{i=2}^n\text{Ans}_1(\frac{n}{i}) \]默认分数下取整.
对于第二个询问,令 \(g=I,h=\epsilon\),则满足 \(h=\mu*g\),带入杜教筛,有
\[\begin{aligned} \text{Ans}_2(n)&=\frac{\sum_{i=1}^nh(i)-\sum_{i=2}^ng(i)\text{Ans}_2(\frac{n}{i})}{g(1)} \\ &=1-\sum_{i=2}^n\text{Ans}_2(\frac{n}{i}) \end{aligned} \]默认分数下取整.
然后打代码就可以了.
代码
const int maxn=2e6;
map<int,ll>mphi,mmu;
ll mu[maxn+5],phi[maxn+5];
int prime[maxn>>2],pcnt;
inline void sieve(){
phi[1]=mu[1]=1;
rep(i,2,maxn){
if(!phi[i])mu[i]=-1,phi[i]=i-1,prime[++pcnt]=i;
for(int j=1;j<=pcnt && i*prime[j]<=maxn;++j){
if(i%prime[j]==0){
mu[i*prime[j]]=0;
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
mu[i*prime[j]]=-mu[i];
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
rep(i,2,maxn)mu[i]+=mu[i-1],phi[i]+=phi[i-1];
}
ll getphi(const int n){
if(n<=maxn)return phi[n];
else if(mphi[n])return mphi[n];
ll ret=1ll*n*(1ll+n)/2;
for(ll l=2,r;l<=n;l=r+1){
r=n/(n/l);
ret-=1ll*(r-l+1)*getphi(n/l);
}
// printf("Now n == %d phi == %lld\n",n,ret);
return mphi[n]=ret;
}
ll getmu(const int n){
if(n<=maxn)return mu[n];
else if(mmu[n])return mmu[n];
ll ret=1;
for(ll l=2,r;l<=n;l=r+1){
r=n/(n/l);
// printf("When n == %d, l == %lld, r == %lld\n",n,l,r);
ret-=(r-l+1)*getmu(n/l);
}
return mmu[n]=ret;
}
int n;
signed main(){
// freopen("shit.out","w",stdout);
phi[1]=mu[1]=1;
sieve();
rep(i,1,readin(1)){
n=readin(1);
writc(getphi(n),' ');
writc(getmu(n),'\n');
}
return 0;
}
用到の一些小 \(\tt trick\)
除了杜教筛板子以外好像没什么 \(\tt trick\) 可说了......