求欧拉函数值

欧拉函数

两个数gcd等于1，即两个数互质1到n中与n互质的数的个数称为欧拉函数记 $\varphi (n)$算数基本定理：$$N=p_1^{c_1}{p}_2^{c_2}{p}_3^{c_3}{p}_4^{c_4}\cdots p_m^{c_m}$$ $$\varphi (n)=N\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_m-1}{p_m}=N\times \prod _{质数p|N}(1-\frac{1}{p})$$当a、b互质时，$\varphi (a\times b)=\varphi (a)\times \varphi (b)$ ，【积性函数】

[SDOI2008]仪仗队 题目链接

线性筛素数的同时求出每个数的欧拉函数值

const int N = 100000 + 10; int phi[N]; int prime[N]; bool vis[N]; //即可以求出素数，还可以求出欧拉函数值 void Euler() { int cnt = 0; phi[1] = 1; for (int i = 2; i < N; i++) { if (vis[i] == false) { prime[cnt++] = i; phi[i] = i - 1; } for (int j = 0; j < cnt && 1LL * prime[j] * i < 1LL * N; j++) { vis[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] * phi[prime[j]]; } } } }

只筛素数，复杂度$O(nlogn)$

int e2[N]; void Euler2() { for (int i = 1; i < N; ++i) { e2[i] = i; } for (int i = 2; i < N; ++i) { if (e2[i] == i) { for (int j = i; j < N; j += i) { e2[j] = e2[j] / i * (i - 1); } } } }

也可以这么写

int e3[N]; void Euler3() { memset(e3, 0, sizeof(e3)); e3[1] = 1; for (int i = 2; i < N; ++i) { if (e3[i] == 0) { for (int j = i; j < N; j += i) { if (e3[j] == 0) { e3[j] = j; } e3[j] = e3[j] / i * (i - 1); } } } }