欧拉函数
在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。
通式：φ(x)=xi=1∏n(1−pi1)其中p1,p2…pn为x的所有质因数，x是不为0的整数。
注意：每种质因数只有一个。比如12=223那么φ(12)= 12 * (1-1/2)*(1-1/3)=4。
定理：
1.如果p是素数，那么φ(p )=p-1；反之如果p是一个正整数且满足φ(p )=p-1，那么p是素数。
2.如果p是素数，a是一个正整数，那么φ(pa)=pa-pa-1。
证明：比pa小的数有pa-1个，因为pa只有一个素因子p，其中与p不互质的个数就是p的倍数个数pa-1-1。
3.设n和m是互质的正整数，那么φ(nm)=φ(n)φ(m)。因为欧拉函数是积性函数。
4.设n=p1a1p2a2…pkak 为正整数n的素数幂分解，那么φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pk)(算法的核心)
5.设n是一个正整数，那么d∣n∑φ(d)=n
6.如果n大于2，那么n的欧拉函数值是偶数。
所以，根据通式可以得到求单个数的欧拉函数
long long Euler(long long n){
long long ans = n;
for(int i = 2; i * i <= n; i++){
if (n % i == 0){
ans -= ans / i;
while(n % i == 0) n /= i;
}
}
if(n > 1) ans -= ans / n;
return ans;
}
而有时候我们会频繁的调用欧拉函数，那我们通常会预处理所有欧拉函数出来
const int MAXN = 3000001;
int euler[MAXN];
void getEluer(){
memset(euler, 0, sizeof(euler));
euler[1] = 1;
for(int i = 2; i <= MAXN; i++){
if(!euler[i])
for(int j = i; j <= MAXN; j += i){
if(!euler[j]) euler[j] = j;
euler[j] = euler[j] / i * (i - 1);
}
}
}
除此之外，我们经常还会通过欧拉筛素数的同时求欧拉函数
const int MAXN = 10000000;
bool check[MAXN + 10];
int phi[MAXN + 10];
int prime[MAXN + 10];//素数
int tot; //素数的个数
void phi_and_prime_table(int N){
memset(check, false, sizeof(check));
phi[1] = 1;
tot = 0;
for(int i = 2; i <= N; i++){
if(!check[i]){
prime[tot++] = i;
phi[i] = i - 1;
}
for(int j = 0; j < tot; j++){
if(i * prime[j] > N) break;
check[i * prime[j]] = true;
if(i % prime[j] == 0){
phi[i * prime[j]] = phi[i] * prime[j];
}
else{
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
}