当前位置：首页 > news >正文

欧拉函数学习笔记

news 2025/9/25 14:05:59

先讲一下欧拉函数的定义：欧拉函数 \(\phi(n)\) 定义为不超过 \(n\) 且与 \(n\) 互质的正整数的个数。

\(\phi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1]\)

例子：

n = 8：小于 \(n\) 的正整数是 [1, 2, 3, 4, 5, 6, 7, 8]。
- 8 和 2 有共同因数 2，不满足。
- 8 和 4 有共同因数 4，不满足。
- 8 和 1, 3, 5, 7 的最大公约数都是 1，所以它们满足。
- 所以 \(\phi(8)=4\) 。

通解式 φ(n) = n * (1 - 1/p₁) * (1 - 1/p₂) * ...这个公式看起来吓人，但它其实就是一个高效的“排除法”。

想象一下：
你要从 1 到 n 中找出所有和 n 互质的数。最笨的办法是一个个检查。但我们可以聪明一点，直接把肯定不是符合的数踢出去。

步骤：

找出 n 的所有质因数。比如 n = 12，它的质因数是 2 和 3。
踢掉所有 2 的倍数：在 1-12 中，2 的倍数有 6 个（12 * 1/2 = 6）。踢掉后，剩下 12 * (1 - 1/2) = 6 个数。
踢掉所有 3 的倍数：在剩下的 6 个人里，有多少是 3 的倍数呢？因为 2 和 3 互质，所以分布是均匀的。所以要再踢掉剩下个数的 1/3。最终剩下 12 * (1 - 1/2) * (1 - 1/3) = 4 个人。

这 4 个人就是 [1, 5, 7, 11]，正好是 φ(12) 的值。这个公式就是一个高效的“筛子”，把所有和 n 有共同质因数的数都筛掉了。

简单理解：质数 p 的"契合度"非常高。因为它除了 1 和它自己，没有其他因数。所以从 1 到 p-1 的所有数都和它满足！只有它自己（p）和它不互质（gcd(p, p) = p）。
例子：p = 7，[1, 2, 3, 4, 5, 6] 全部和它满足，所以 φ(7) = 6。

这是最难直观理解的一点，但可以用一个二维网格来想象。

想象一个 m 行 n 列的网格，总共有 m * n 个格子。我们可以用坐标 (i, j) 来表示每个格子，其中 1 ≤ i ≤ m, 1 ≤ j ≤ n。
问题：有多少个格子 (i, j) 满足 gcd(i, j) = 1？这其实就等价于 φ(m*n)（在特定条件下）。
关键洞察：因为 m 和 n 互质，根据中国剩余定理，gcd(i, j) = 1 当且仅当 gcd(i, m) = 1 并且 gcd(j, n) = 1。
所以：满足条件的格子数 = （i 的合法选择数） * （j 的合法选择数） = φ(m) * φ(n)。

虽然这个解释用到了一点高级概念，但你可以把它理解为：当两个数 m 和 n 没有任何共同的“麻烦”（互质）时，它们的“契合度”大小可以直接相乘，不会互相干扰。

接下来讲一个例题：P2158仪仗队

p[1] = 1; // 1要特判

for(re int i=2; i<=n; ++i)

if(!b[i]) // 这代表i是质数
{prime[++num] = i;p[i] = i - 1;
}

变量说明：
- b[] 是一个布尔标记数组（通常初始化为 false）。b[i] == true 表示 i 是合数。
- prime[] 数组用于存储找到的质数。
- num 是已找到质数的计数器。
逻辑：
- 如果 b[i] 为 false，说明 i 没有被任何更小的质数筛掉，因此 i 本身是一个质数。
- 将 i 加入质数数组 prime。
- 关键：对于任意质数 p，φ(p) = p - 1。因为从 1 到 p-1 的所有整数都与 p 互质。

这是线性筛的核心部分，通过已知的质数 prime[j] 去筛掉 i * prime[j] 这个合数，并同时计算 p[i * prime[j]]。

for(re int j=1; j<=num && prime[j]*i<=n; ++j)
{b[i * prime[j]] = 1; // 先把这个合数标记掉...
}

解释：内层循环遍历所有已找到的质数 prime[j]，尝试用 prime[j] 去乘 i，生成一个新的合数 i * prime[j]，并将其标记为合数。

接下来是计算欧拉函数值的关键分支，它基于 i 和 prime[j] 的关系，利用了欧拉函数的两个核心性质。

if (i % prime[j] == 0)
{p[i * prime[j]] = p[i] * prime[j];break;
}

数学原理：假设 i 已经包含了质因子 prime[j]，即 i = prime[j]^k * m（其中 m 与 prime[j] 互质）。那么 i * prime[j] = prime[j]^(k+1) * m。
根据欧拉函数的通式：
- φ(i) = i * (1 - 1/prime[j]) * ... （... 代表 m 的其他质因子部分）
- φ(i * prime[j]) = i * prime[j] * (1 - 1/prime[j]) * ... = prime[j] * φ(i)
结论：当 prime[j] 整除 i 时，φ(i * prime[j]) = φ(i) * prime[j]。
break 的作用：这是线性筛保证线性时间复杂度的核心。因为 prime[j] 是 i 的最小质因子（筛法的性质），所以 prime[j] 也是 i * prime[j] 的最小质因子。为了确保每个合数只被其最小的质因子筛掉一次，我们在此处 break，不再用更大的质数去乘 i。

else
{p[i * prime[j]] = p[i] * p[prime[j]];
}

数学原理：此时 i 和 prime[j] 互质（因为 prime[j] 是质数且不能整除 i）。
关键性质：欧拉函数是一个积性函数。这意味着，如果 gcd(a, b) = 1，那么 φ(a * b) = φ(a) * φ(b)。
结论：因为 gcd(i, prime[j]) = 1，所以 φ(i * prime[j]) = φ(i) * φ(prime[j])。而 φ(prime[j]) = prime[j] - 1，这个值在 prime[j] 被识别为质数时就已经计算并存储在 p[prime[j]] 中了。