欧拉函数学习笔记
1.定义
先讲一下欧拉函数的定义:欧拉函数 \(\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\) 。
2.理通解式
通解式 φ(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
有共同质因数的数都筛掉了。
三、理解两个核心性质
性质1:如果 p
是质数,那么 φ(p) = p - 1
- 简单理解:质数
p
的"契合度"非常高。因为它除了1
和它自己,没有其他因数。所以从1
到p-1
的所有数都和它满足!只有它自己(p
)和它不互质(gcd(p, p) = p
)。 - 例子:
p = 7
,[1, 2, 3, 4, 5, 6]
全部和它满足,所以φ(7) = 6
。
性质2:欧拉函数是“积性函数”(当 m
和 n
互质时,φ(m*n) = φ(m) * φ(n)
)
这是最难直观理解的一点,但可以用一个二维网格来想象。
- 想象一个
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仪仗队
1. 初始化与特判
p[1] = 1; // 1要特判
- 解释:根据欧拉函数的定义,
φ(1) = 1
。因为小于等于1且与1互质的正整数只有1本身。这是一个基础的边界条件,需要单独处理。
2. 主循环:遍历每个数 i
for(re int i=2; i<=n; ++i)
- 解释:从
2
开始遍历到n
。2
是最小的质数。
3. 判断 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
互质。
- 如果
4. 筛选合数并计算其欧拉函数
这是线性筛的核心部分,通过已知的质数 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]
的关系,利用了欧拉函数的两个核心性质。
情况一:prime[j]
是 i
的质因子 (i % prime[j] == 0
)
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
。
情况二:prime[j]
与 i
互质 (i % prime[j] != 0
)
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]]
中了。