Number theory template

Seek single phi( It's big )

inline ll getphi(ll x){
    
    ll res=x;
    for(ll i=2;i*i<=x;i++){
    
        if(x%i==0){
    
            res=res/i*(i-1);
            while(x%i==0) x/=i; 
        }
    }
    if(x>1) res=res/x*(x-1);
    return res;
}

Ask for a group phi Very small

void get_phi()  
{
      
    int i, j, k;  
    k = 0;  
    for(i = 2; i < maxn; i++)  
    {
      
        if(is_prime[i] == false)  
        {
      
            prime[k++] = i;  
            phi[i] = i-1;  
        }  
        for(j = 0; j<k && i*prime[j]<maxn; j++)  
        {
      
            is_prime[ i*prime[j] ] = true;  
            if(i%prime[j] == 0)  
            {
      
                phi[ i*prime[j] ] = phi[i] * prime[j];  
                break;  
            }  
            else  
            {
      
                phi[ i*prime[j] ] = phi[i] * (prime[j]-1);  
            }  
        }  
    }  
} 

Euler sieve gets prime number table

void get_prime()       // Euler sieve gets prime number table 
{
    
    memset(vis,0,sizeof(vis));
    tot=0;
    for(int i=2;i<=maxn;i++)
    {
    
        if(!vis[i])
            prime[++tot]=i;
        for(int j=1;j<=tot&&i*prime[j]<=maxn;j++)
        {
    
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)
                break;
        }
    }
}

Solving Mobius function by linear sieve

void init(){
    // Linear sieve Mobius function 
	f[1]=mu[1]=1;
	for(int i=2;i<=N;i++){
    
		if(vis[i]==0){
    
		    prime[++cnt]=i;
		    mu[i]=-1;// A single mu value 
		}
		for(int j=1;j<=cnt;j++){
    
			if(i*prime[j]>N)break;
			vis[i*prime[j]]=1; 
			mu[i*prime[j]]=i%prime[j]?-mu[i]:0;
			if(i%prime[j]==0)break;
		}
		f[i]=f[i-1]+mu[i];// The prefix and 
	}
}