int phi[maxn+5],prime[maxn+5],cnt; bool notp[maxn+5]; void getphi() { phi[1]=1,cnt=0; for(int i=2;i<=maxn;i++) { if(!notp[i]) { prime[++cnt]=i; phi[i]=i-1; } for(int j=1;j<=cnt&&i*prime[j]<=maxn;j++) { notp[i*prime[j]]=1; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j];break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } }