Cacher is the code snippet organizer for pro developers

// 欧拉函数：（要求gcd(x,p)==1，即x、p互素）

// 令ϕ(m)表示小于等于m且与m互素的正整数的个数。
// 如果x和m互质，则有xϕ(m)≡1(mod m)，即x×xϕ(m)−1≡1(modm)，xϕ(m)−1即为x的逆元。
// 在m为质数的情况下，ϕ(m)=m−1，即为费马小定理。


// 对于任意整数n，可以将它分解n=pk11∗pk22∗pk33...pkmm，其中pi为质数。

// 其中ϕ(n)=ϕ(p1k1)∗ϕ(pk22)...ϕ(pkmm)

// 最后转化为ϕ(n)=n∗∏(pi−1)/pi
void Make_phi(){  
    phi[1]=1;not_prime[1]=true;  
    for(int i=2;i<=maxn;i++){  
        if(!not_prime[i]){  
            prime[++prime[0]]=i;  
            phi[i]=i-1;  
        }  
        for(int j=1;j<=prime[0];j++){  
            if(i*prime[j]>maxn)break;  
            not_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);  
            }  
        }  
    }  
}  

// 2.费马小定理：

// 在p是素数的情况下，对任意整数x都有xp≡x(mod)p。
// 如果x无法被p整除，则有xp−1≡1(mod p)。
// 可以在p为素数的情况下求出一个数的逆元，x∗xp−2≡1(mod p)，xp−2即为逆元。
int phi(int n){  
    int res=n;  
    for(int i=2;i*i<=n;i++){  
        if(!(n%i)){  
            res=res*(i-1)/i;  
            while(!(n%i))n/=i;  
        }  
    }  
    if(n!=1)res=res*(n-1)/n;    //说明n是质数  
    return res;  
}  

// 求x对于mod p的逆元：

// 1.扩展欧几里得：（要求gcd(x,p)==1，即x、p互素）
int exgcd(int a,int b,int &x,int &y){  
    if(!b){  
        x=1;y=0;  
        return a;  
    }  
    int re=gcd(a,b,y,x);  
    y-=a/b*x;  
    return re;  
}  
int inv(int x,int p){  
    int iv,temp;  
    exgcd(x,p,iv,temp);  
    return (iv%p+p)%p;  
}  

// 线性逆元递推：（O(n)求出1~n内所有数对于mod p的逆元）

// inv[1]=1

// inv[n]=(p-p/n)*inv[p%n]%p
int inv[maxn],mod;

void Make_inv(int max){
	inv[1]=1;
	for(int i=2;i<=max;i++)
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

// 线性筛选素数
int prime[maxn];
bool not_prime[maxn];

void Make_prime(int max){     //筛出1到max内的所有素数储存在prime中，prime[0]为素数数量
	not_prime[1]=true;
	for(int i=2;i<=max;i++){
		if(!not_prime[i])
			prime[++prime[0]]=i;
		for(int j=1;j<=prime[0]&&prime[j]*i<=max;j++){
			not_prime[prime[j]*i]=true;
			if(!(i%prime[j]))break;
		}
	}
}