欧拉函数 \(\varphi\) 的定义，\(\varphi(i)\) 表示从 \([1, i]\) 之间和 \(i\) 互质的数的数量 （ \(a\) 和 \(b\) 互质即 \(\gcd(a, b) = 1\)）。欧拉函数是积性函数，例如 \(a, b\) 都为质数，那么 \(φ(ab) = φ(a) \times φ(b)\)，递推式为
\[φ(ab) = \frac {φ(a) \times φ(b) \times \gcd(a,b)}{φ(\gcd(a,b))} \]（证明暂时搁置）
设一个数 \(N\) 可得
\[N = p_1^{b_1} \times p_{2}^{b_2} \times p_{3}^{b_3} \times \ldots \times p_{k}^{b_k} \quad p为质数 \]因为
\[\displaylines{ \varphi(N) = \varphi(p_1^{b_1}) \times \varphi(p_2^{b_2}) \times \varphi(p_3^{b_3}) \times \ldots \times \varphi(p_k^{b_k}) \\ \varphi(p^b) = p^b - p^{b-1} } \]还因为 \([1, p^b]\) 一共有 \(p^b\) 个数，不和 \(p^b\) 互质的数有 \(1 \times p, 2 \times p, 3 \times p, \ldots, p^{b-1} \times p\) , 总共 \(p^{b-1}\) 个, 剩下的就是满足要求的即 \(p^b - p^{b-1}\) 个数。
即
\[φ(p^b) = p^b \times (1 - \frac{1}{p}) \]可得
\[\varphi(N) = p_1^{b_1} \times (1 - \frac{1}{p_1}) * p_2^{b_2} * (1 - \frac{1}{p_2}) \times \ldots p_k^{b_k} * (1 - \frac{1}{p_k}) \]就等于
\[\varphi(N) = (p_1^{b_1} \times p_2^{b_2} \times \ldots * p_k^{b_k}) \times (1 - \frac{1}{p_1}) * (1 - \frac{1}{p_2}) \times \ldots \times (1 - \frac{1}{pk}) \]又因为
\[N = p1^b1 * p2^b2 * ... * pk^bk \]可得
\[\varphi(N) = N * (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \ldots \times (1 - \frac{1}{p_k}) \]就可以通过分解 \(N\) 的质因数求出来 \(\varphi(N)\)，由此也可以看出，一个数的欧拉函数的大小和质数的次幂无关。
试除法分解质因数是 \(O(\sqrt n)\) 的, 所以求 \(\varphi(N)\) 也就是 \(O(\sqrt n)\) 的
具体见代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m;
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n;
int res = n;
for (int i = 2; i <= n / i; i ++ )
{
if (n % i == 0)
{
res = res / i * (i - 1); // 相当于res * (1 - 1 / i), 这样是为了防止出现小数, 下取整没了, 最主要的就是这里
while (n % i == 0) n /= i;
}
}
if (n != 1) res = res / n * (n - 1); // 这里不要忘记
cout << res << endl;
}
return 0;
}
一个数欧拉函数的大小和质因数的次幂无关
筛法求欧拉函数
\(O(n)\)
这里写的注释很好，就不多重打了。
是用线性筛顺便筛出欧拉函数，首先，线性筛可以筛出质数 p，质数的欧拉函数很好求，因为一个质数在 \([1, p]\) 中除了 p 本身以外，其他所有数都与它互质，所以 \(\varphi(p) = p - 1\)。
而对于筛掉的数，我们可以知道，筛掉的数是用这个数 u 的最小质因子 p 筛去的，唉？质因子是质数吧，按算法运行顺序来说， u 是由 \(p \times i\) 得到的，那么 i 是整数，且肯定比 u 小，按理说，它的欧拉函数我已经求出来了。而 \(\varphi(p) = p - 1\)，我们还知道一个等式。
即
那么就可以得出来了
\[\varphi(u) = \varphi(i \times p) = \frac {\varphi(p) \times \varphi(i) \times \gcd(p,i)}{\varphi(\gcd(i,p))} \]其中因为 \(p\) 是质数，而 \(p <= i\) ，并且 p 是 i 的质因子，所以 \(\gcd(i,p) = p\)，所以 \(\varphi(\gcd(p,i)) = \varphi(p)\)
所以有下式
在注释里还有一种解释方法，这里就不说了。
/*
线性筛可以求出很多附加的东西
具体会在代码里写注释
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010;
int n;
int primes[N], cnt;
bool st[N];
int phi[N]; // phi[i] 是i的欧拉函数
LL sum;
int main()
{
cin >> n;
phi[1] = 1; // 1的欧拉函数是1, 需要手动写上
for (int i = 2; i <= n; i ++ )
{
if (st[i] == 0)
{
primes[ ++ cnt] = i;
sum += phi[i] = i - 1; // 首先如果i是质数, 质数和所有数都互质(除了它自己), 那么对于质数i的φ, 就是i - 1
}
for (int j = 1; primes[j] <= n / i; j ++ )
{
st[i * primes[j]] = true;
if (i % primes[j] == 0) // 如果i % pj == 0 那么pj就是i的最小质因数(这点在线性筛里提到过)
{ // 说明i的质因数包括pj, 那么φ(i)里面包括 (1 - 1/pj), 一个数欧拉函数的大小和其质因数的次幂无关, 根据φ(N) = N * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk);
sum += phi[i * primes[j]] = phi[i] * primes[j]; // pj * i 比 i 只多了一个pj而且pj还在i的质因数里面, 那么 φ(i*pj)只比φ(i)多一个pj 也就是 φ(i*pj) = φ(i) * pj
break;
}
sum += phi[i * primes[j]] = phi[i] * (primes[j] - 1); // 和上面同理, 但是pj不是i的质因数, 所以φ(i) 不包含 (1 - 1/pj), φ(pj*i)需要加上这个
}
}
cout << sum + 1 << endl;
return 0;
}