省选模板_简单数学

//线性筛(欧拉函数，莫比乌斯函数)
namespace get_prime{
    int tot; 
    int prime[maxn],is[maxn];
    int mu[maxn],phi[maxn]; 
    void get_prime(){
        mu[1]=1; 
        phi[1]=1; 
        for(int i=2;i<maxn;++i){
            if(!is[i]) {
                prime[++tot]=i;
                phi[i]=i-1;
                mu[i]=-1; 
            }
            for(int j=1;j<=cnt&&prime[j]*i<maxn;++j){
                is[prime[j]*i]=1; 
                if(i%prime[j]!=0) {
                    phi[i*prime[j]]=phi[i]*(prime[j]-1); 
                    mu[i*prime[j]]=-mu[i]; 
                }
                else {
                    phi[i*prime[j]]=prime[j]*phi[i]; 
                    mu[i*prime[j]]=0; 
                    break; 
                }
            }
        }
    }
};