测试2

欧拉函数

互质：对于 $forall a, b in mathbb{N} $， 若 (a, b) 的最大公因数为 (1) ， 则称 (a, b) 互质。

欧拉函数:即 $ varphi (N)$, 表示从 (1) 到 (N) 中与 (N) 互质的数的个数。

在算术基本定理中， 任何一个大于 (1) 的整数都可以唯一分解为有限个质数的乘积， 写作；

[N = p_1^{c_1}p_2^{c_2} ldots p_m^{c_m} ]

其中， (p_i) 为质数， (c_i) 为正整数， 且 $ p_1 < p_2 < ldots <p_m $ 。

于是就有一个公式：

[varphi(N) = N cdot frac{p_1 - 1}{p_1} cdot frac{p_2 - 1}{p_2} cdot ldots cdot frac{p_m - 1}{p_m} = N cdot prod_{text{质数}p|N}^{} (1 - frac{1}{p}) ]

证法一

首先一个数要与 (N) 互质的数， 则充要条件是它的质因子都不会在 (N) 的质因子当中出现。因此，我们只需要将 (N) 分解每个质因子 (p_i) ， 再从 (1 sim N) 中去除可以被 (p_i) 整除的数，最后剩下的就一定都是与 (N) 互质的数了。当我们去除 (1 sim N) 中与被 (p_1) 整除的数时，(1 sim N) 中 (p) 的倍数 (p_1, 2p_1, 3p_1, ldots N / p_1 cdot p_1) 这 $ N / p_1 $ 个数都会被去除。则此时 (N) 中质因子不包括 (p_1) 的数有 $ N - frac{N}{p_1}$个。同理， 当我们去除 (1 sim N) 中与被 (p_2) 整除的数时，也会去除 (N / p_2) 个数。但若有数即使 (p_1) 也是 (p_2) 的倍数, 即 (p_1 cdot p_2) 的倍数，就会被去除 (2) 次，因此还要加回来一次。这时 (1 sim N) 中不含有质因子 (p_1) 与 (p_2) 的数的个数为：

[N - frac{N}{p_1} - frac{N}{p_2} + frac{N}{p_1p_2} = N * (1 - frac{1}{p_1} - frac{1}{p_2} + frac{1}{p_1p_2}) = N(1 - frac{1}{p_1})(1 - frac{1}{p_2}) ]

依次类推，类似的读者也可以自己试着推一下当去除 (p_3) 的倍数的情况，这样一直推下去，就能推出上面的公式。给一个更好理解的方式：
设 $ 1 sim N$ 中的一个整数 (a) 能被 (k) 个 (N) 的质因子整除，于是它的去除次数就是：

[C_{k}^{1} - C_{k}^{2} + C_{k}^{3} - ldots + (-1) ^ k - 1 cdot C_{k}^{k} = 1 ]

上式由二项式定理可得。（别问，我也不会QAQ，初三OIer瑟瑟发抖）

这就保证了每个质因子包含了 (N) 的质因子的数有且只会被去除一次。

这种思想就叫做容斥原理。长这样：


应该都能看懂吧 ，看懂的扣1，看不懂的扣眼珠子，我才不会说我是懒

证法二

欧拉函数有一个性质，即它是积性函数。

积性函数：对于任意互质的整数 (a) 和 (b) 有性质(f(ab)=f(a)cdot f(b))的数论函数。

证明如下：

设 (a) 的所有质因子为(left {p_1, p_2, ldots, p_{m1} right }) , (b) 的所有质因子为 (left{q_1, q_2, ldots, q_{m2} right}), (ab) 的所有质因子为(left{r_1, r_2, ldots, r_{m3} right}) 。则：

[varphi(a) = a cdot frac{p_1 - 1}{p_1} cdot frac{p_2 - 1}{p_2} cdot ldots cdot frac{p_{m1} - 1}{p_{m1}} ]

[varphi(b) = b cdot frac{q_1 - 1}{q_1} cdot frac{q_2 - 1}{q_2} cdot ldots cdot frac{q_{m2} - 1}{q_{m2}} ]

[begin{aligned} varphi(a) cdot varphi(b) &= a cdot frac{p_1 - 1}{p_1} cdot frac{p_2 - 1}{p_2} cdot ldots cdot frac{p_{m1} - 1}{p_{m1}} cdot b cdot frac{q_1 - 1}{q_1} cdot frac{q_2 - 1}{q_2} cdot ldots cdot frac{q_{m2} - 1}{q_{m2}} \ &=ab cdot frac{p_1 - 1}{p_1} cdot frac{p_2 - 1}{p_2} cdot ldots cdot frac{p_{m1} - 1}{p_{m1}}cdot frac{q_1 - 1}{q_1} cdot frac{q_2 - 1}{q_2} cdot ldots cdot frac{q_{m2} - 1}{q_{m2}} end{aligned} ]

[varphi(ab) = ab cdot frac{r_1 - 1}{r_1} cdot frac{r_2 - 1}{r_2} cdot ldots cdot frac{r_{m3} - 1}{r_{m3}} ]

因为 (a) 与 (b) 互质，所以对于任意的 (a) 的质因子 (p_i), (b) 的质因子(q_j), 都有 (p_i ne q_j)。因此， (ab)的所有质因子 (left {r_1, r_2, ldots, r_{m3} right } = left {p_1, p_2, ldots, p_{m1} right } + left {q_1, q_2, ldots, q_{m2} right }) 。

因此，

[frac{p_1 - 1}{p_1} cdot frac{p_2 - 1}{p_2} cdot ldots cdot frac{p_{m1} - 1}{p_{m1}}cdot frac{q_1 - 1}{q_1} cdot frac{q_2 - 1}{q_2} cdot ldots cdot frac{q_{m2} - 1}{q_{m2}} = frac{r_1 - 1}{r_1} cdot frac{r_2 - 1}{r_2} cdot ldots cdot frac{r_{m3} - 1}{r_{m3}}]

即：

[varphi(ab) = varphi(a) cdot varphi(b) ]

证毕。

由算术基本定理，

[N = p_1^{c_1}p_2^{c_2} ldots p_m^{c_m} ]

对于每项 (varphi(p_i^{c_i}))， 从定义出发，表示从(1 sim p_1^{c_1}) 之间所有与 (p_1^{c_1}) 互质的数的个数。因为 (p_1) 为质数，所以只有 (p_1) 的倍数才是不与 (p_1 ^ {c_1}) 互质的数。因此(varphi(p_i^{c_i}) = p_i^{c_i} - p_i^{c_i - 1})。

于是

[begin{aligned} N &= (p_1^{c_1} - p_1^{c_1 - 1})(p_2^{c_2} - p_2^{c_2 - 1}) ldots(p_m^{c_m} - p_m^{c_m - 1}) \ &=p_1^{c_1}(1- frac{1}{p_1})p_2^{c_2}(1 - frac{1}{p_2}) ldots p_m^{c_m}(1 - frac{1}{p_m}) \ &=p_1^{c_1}p_2^{c_2} ldots p_m^{c_m}prod_{i = 1}^{m}(1 - frac{1}{p_i}) \ &=N cdot prod_{text{质数}p|N}^{}(1 - frac{1}{p}) end{aligned} ]

欧拉定理

欧拉定理：若 (gcd(a, m) = 1) ， 则 $ a ^ {varphi(m)} equiv 1 pmod{m}$

这里就需要一丢丢数论基础，让我来稍做补充（日后另开一篇）：

  • 剩余系：对于任意正整数 (m) ，一个数除以 (m) 所得的余数只能是 $ 0, 1, 2, ldots, m - 1 $ 中的某一个，因此可以将整数分为 (m) 个类。每个类叫做剩余类。从中任选任意多个类，从这些类中各取一个数，构成一个集合，就将这个集合称为模 (m) 的剩余系。
  • 完全剩余系（完系）：从模 (m) 的 (m) 个类中，每类各取 (1) 个数所构成的集合就算模 (m) 的一个完全剩余系，简称为模 (m) 的完系。
  • 简化剩余系（缩系）：如果一个模 (m) 的剩余类中存在一个与 (m) 互素的剩余，该类叫做简化剩余类；在模 (m) 的所有不同简化剩余类中，从每个类任取一个数组成的整数的集合，叫做模 (m) 的一个简化剩余系。容易得出， 模 (m) 共有 (varphi(m)) 个简化剩余类。

证明：

设 (r_1, r_2, ldots, r_{varphi(m)}) 为模 (m) 意义下的一个简化剩余系， 即(r_1, r_2, ldots, r_{varphi(m)})之前互不相同且都与 (m) 互为质数， 那么，对于任意 (r_i, r_j(i ne j)), 与 (a) 的乘积 (ar_i, ar_j) 不相等, 且仍然与 (m) 互质（注意， (a) 与 (m) 互质， 我就因为没注意到这个懵逼了好久QAQ)，因此， (ar_1, ar_2, ldots , ar_{varphi(m)})也是模 (m) 意义下的一个简化剩余系，则

[begin{aligned} r_1r_2 ldots r_{varphi(m)} &equiv ar_1ar_2 ldots ar_{varphi(m)}\ &equiv a^{varphi(m)}(r_1r_2ldots r_m) pmod{m} end{aligned}]

约去((r_1r_2ldots r_m)), 得

[1 equiv a ^ {varphi(m)} pmod{m} ]

证毕。

同时，我们还可以用欧拉定理推出费马小定理：

费马小定理： 若 (p) 为素数， (gcd(a, p) = 1), 则 $a^{p - 1} equiv 1 pmod{p} $

当 (p) 为素数时，很显然， (varphi(p) = p - 1)， 因此就有：

[a^{varphi(p)} equiv 1 pmod{p} ]

就变成了欧拉定理！

参考书籍及网站：《算法竞赛进阶指南》,小蓝本初中卷, OI Wiki, AcWing。

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/yduck/p/17607470.html

标签： 算法 数据结构
你还没有登录，请先登录或注册！
  • 还没有人评论，欢迎说说您的想法！

相关课程

英特尔® OpenVINO™工具套件初级课程
293354 0元 限免
基于 OpenVINO™ 的 AI 视觉应用进阶课
42074 0元 限免