欧拉函数:phi(n) = the number of i where gcd(i,n) = 1 and 1 <= i <= n.
解法:容斥原理。
先将 n 分解质因数,然后 phi(n) = Σphi(p_i) - Σphi(p_i * p_j) + Σphi(p_i * p_j * p_k) - ... 。
可简化成式子 phi(n) = n * (1 - 1/pi) * (1 - 1/pj) * ... 。
在线版。
#include <stdio.h> int euler(int n) { int ret = n; for(int i=2;i*i<=n;i++) { if(n % i == 0) { ret = ret / i * (i - 1); while(n % i == 0) n /= i; } } if(n != 1) ret = ret / n * (n - 1); return ret; }
预处理版。
#include <stdio.h> const int N = 1e5 + 5; int phi[N]; void pre_euler() { phi[1] = 1; for(int i=2;i<N;i++) { if(!phi[i]) { for(int j=i;j<N;j+=i) { if(!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i - 1); } } } }
欧拉函数的和:phi_sum(n) = the sum of phi(i) where gcd(i,n) = 1 and 1 <= i <= n.
phi_sum(n) = n * phi(n) / 2 (n >= 2) .
phi_sum(n) = 1 (n == 1) .