求单个数的欧拉函数
ll getoula(ll n) { if(n==1) return 0; ll ans=n; for(int i=2;i<=(int)sqrt(n+0.5);++i) { if(n%i==0) { ans = ans * (i-1)/i; while(n%i==0) n/=i; } } if(n>1) ans = ans *(n-1) /n; return ans; } 求区间欧拉函数 int phi[maxn]; int p[maxn],pnum; bool book[maxn]; void prime() { memset(book,0,sizeof(book)); pnum=0; phi[1]=1; for(int i=2;i<maxn;++i) { if(!book[i]) { p[pnum++]=i; phi[i]=i-1; } for(int j=0;j<pnum && p[j]*i<maxn ;++j) { book[p[j]*i]=1; if(i % p[j]==0) { phi[i*p[j]]=phi[i]*p[j]; break; } else phi[i*p[j]] = phi[i] * (p[j]-1); } } }求莫比乌斯函数
void getprime() { memset(book,1,sizeof(book)); cnt=0; mu[1]=1; for(int i=2;i<maxn;++i) { if(book[i]) { p[cnt++]=i; mu[i]= -1; } for(int j=0; j<cnt && i*p[j]<maxn;++j) { book[i*p[j]]=0; if(i %p[j]==0) { mu[i *p[j]]= 0; break; } else mu[i*p[j]] = -mu[i]; } } }
