欧拉函数模板

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

ll _phi(ll x) {	//递推求欧拉函数   利用了欧拉函数的积性 
//如果b质数  a%b！=0  phi(a*b) = phi(a)*b - phi(a)
//当b是质数，a%b==0，phi(a*b)=phi(a)*b 
	if (x == 0) return 0;
	ll res = 1, t = x;
	for (ll i = 2; i <= (ll)sqrt(1.*x); i++) {
		if (t%i == 0) {
			res *= (i - 1);
			t /= i;
			while (t%i == 0) {
				res *= i;
				t /= i;
			}
		}
		if (t == 1) break;
	}
	if (t > 1) { res *= (t - 1); }
	return res;
}

ll phi[maxn]; 
void init()
{
	for(int i=1;i<=maxn;i++)
		phi[i] = i;
	for (int i = 2; i*i < maxn; i++){  //最大素因子表
		if (phi[i] == i){
			for (int j = i * i; j < maxn; j += i){
				phi[j] = i;
			}
		}
	}
	phi[1] = 1;
	for (int i = 2; i < maxn; i++){
		if ((i / phi[i]) % phi[i] == 0){
			phi[i] = phi[i / phi[i]] * phi[i];    //当b是质数，a%b==0，phi(a*b)=phi(a)*b 
		}
		else {
			phi[i] = phi[i / phi[i]] * (phi[i] - 1);  //如果b质数  a%b！=0  phi(a*b) = phi(a)*b - phi(a) 
		}
	}
}