约数
灵乌路空
2019-05-15 10:07:14
## $$ \large \text{ 约数:} $$
gyh实在是太 ⑨ 了,没脑子的他只能整理在这里:
如果以下内容中存在错误 ， 请及时通知博主 ， 博主会非常感谢您的指正 ， 并欢迎您把蠢货博主的头 **拧下来**
于 $2019.5.15$ 创建
于 $2019.5.16$ 更新了 **欧拉函数**
------------
$$ \text{从此开始，一个天文单位} $$
$$ \large\downarrow $$
------------
- ### 约数与倍数:
**定义:如果 $a\mid b$ , 则$a$是$b$的约数,$b$是$a$的倍数**
特别地 ，任何正整数都是 $0$ 的约数
一般地，有$1\mid a$ 与 $a\mid a$ 则 $1,a$ 被称为$a$的平凡因子
- ##### 约数的几种求法：
- 试除法(枚举)
枚举 $[1,n]$ 中所有整数 ， 进行试除，判断 $n$ 能否被整除
时间复杂度为 $O(n)$
考虑一波优化 :
设 $d≥ \sqrt x $ 是 $x$ 的约数，那 $\frac{x}{d} ≤ \sqrt x$ 也是 $x$ 的约数，
也就是说，约数是成对出现的，除了完全平方数,完全平方数的根下完全平方数是单独出现的。
所以我们只需要枚举 $i=[\ 1,\sqrt x\ ]$ 判断即可。
时间复杂度为 $O( \sqrt n )$
- 求区间 $[1,n]$中所有数的约数
显然 ，上面的试除法复杂度就变成了$O( n\sqrt n )$
考虑一种更快速的做法 ：
我们可以发现，1 到 n 中以一个数 x 为约数的数 $ x, 2x,3x …… \lfloor \frac{n}{x} \rfloor \times x $
则：当枚举到 $x$ 时，枚举 $x$ 的倍数 , 使他们的约数加上一个 $x$ .
时间复杂度 $O(n\ logn)$ 。
- ##### 对于任意数 $n$ , 求其约数的个数:
通项公式：$num=∑^i_n(ai+1)$
- 证明:
先将 $n$ 质因数分解 , 得到:$n=p_1^{a1}\times p_2^{a2}\times ...$
则：其任意一因子p可表示为：
$p=p_1^{b1}\times p_2^{b2}\times ... (0=<b1<=a1,0=<b2<=a2,...)$
根据 $b1,b2,...$的取值 , 则其因子个数为:
$(a1+1)\times(a2+1)\times...$
- ##### 对于任意数 $n$ ,求其约数和：
通项公式：$sum=\prod_{i=1}^n\sum_{j=0}^{a_i}p_i^j$
- 证明 :
同上 , 先将 $n$ 质因数分解 , 得到:$n=p_1^{a1}\times p_2^{a2}\times ...$
则：其任意一因子p可表示为：
$p=p_1^{b1}\times p_2^{b2}\times ... (0=<b1<=a1,0=<b2<=a2,...)$
根据乘法原理，可得它们的和为:
$(p1^0+p1^1+…p1^a1)(p2^0+p2^1+…p2^a2)…(pk^0+pk^1+…pk^ak)$
即: $sum=\prod_{i=1}^n\sum_{j=0}^{a_i}p_i^j$
**举个贴切的例子 :**
现在要求 $6$ 的约数和:
先质因数分解: $12=2^1\times 3^1$
则其因数为 : $2^0\times3^0\ $ , $\ 2^1\times3^0\ $ , $\ 2^0\times3^1\ $ , $\ 2^1\times3^1\ $
其约数和为 :
$\ \ \ \ 2^0\times3^0\ + \ 2^1\times3^0\ + \ 2^0\times3^1\ + \ 2^1\times3^1\ $
$=3^0\times (2^0+2^1)+3^1\times(2^0+2^1)$
$=(2^0+2^1)(3^0+3^1)$
即通项公式 。
- ### 最大公约数 与 最小公倍数:
- ###### 最大公约数:
**定义：有$n,m$两整数 , $n,m$ 的最大公约数 $d$ 为: 满足 $d\mid n$ 且 $d\mid m$ 的最大的 $d$ ,记作:$d = gcd(n,m)$ ，简写为：$(n,m)$.**
设 $n=p_1^{a1}\times p_2^{a2}\times ...$ ；$m=p
_1^{b1}\times p_2^{b2}\times ... $；
$d=p_1^{c1}\times p_2^{c2}\times ...$
则：若每个$ci<=min(ai,bi)$,则$d$为 $n,m$ 的一个因子.
当每个$ci=min(ai,bi)$,则$d$为 $n,m$ 的最大公约数.
即 : $d= p_1^{min(a1,b1)}\times p_2^{min(a2,b2)}\times ...$
则: $n,m$的最大公约数 , 即: 将$n,m$ 质因数分解后 , 各质数取其在$n,m$ 中的最小值 , 产生的数.
- ###### 求法：
见 [欧几里得 与 扩展欧几里得 - 核融合炉心 - 洛谷博客](https://www.luogu.org/blog/koishikoishi/ou-ji-li-dei-yu-kuo-zhan-ou-ji-li-dei)
- ###### 最小公倍数：
**定义 : 有$n,m$两整数 , $n,m$ 的最小公倍数 $l$ 为: 满足 $n\mid l$ 且 $m\mid l$ 的除 $0$ 以外的最小的 $l$ ,记作:$l = lcm(n,m)$ .简写为：$[n,m]$**
由上,可知: $l= p_1^{max(a1,b1)}\times p_2^{max(a2,b2)}\times ...$
- ###### 性质:
从质因数分解角度考虑 ,由上 , 易证:
$gcd(n,m) \times lcm(n,m)$ $= n \times m$
- 证明：
$gcd(n,m) \times lcm(n,m)$
$= p_1^{min(a1,b1)}\times p_2^{min(a2,b2)}\times ...
\times p_1^{max(a1,b1)}\times p_2^{max(a2,b2)}\times ...$
$=p_1^{a1+b1} \times p_2^{a2+b2} \times ...$
$= n \times m$
- ### 互质
**定义:若 $a,b$ 之间 , 除 $1$ 外,没有其他的公因数 , 则称 $a,b$ 之间互质 . 记为 $a \perp b$ .**
即 : 当 $a,b$ 进行 质因数分解后 , 没有对应相等的质数。
如 : $32 = 2^5$ , $45 = 3^2 \times 5^1$ ， $32,45$就是一对互质的数.
- ###### 性质
- 对于两个不同的质数 $m$ 和 $n$ ，有 $m$ 与 $n$ 互质。
- 对于任意两个相邻的整数 $m$ 和 $n$，有 $m$ 与 $n$ 互质。
- 对于任意一个自然数 $m$，有 $1$ 与 $m$ 互质。
- 一个质数 $m$ 和一个合数 $n$，若 $n$ 不是 $m$ 的倍数，则 $m$ 与 $n$ 互质。
- ### 欧拉函数
**定义：对于正整数 $n$，满足 $ a\perp n $ 的 a 的个数 $(a < n)$，即为 $n$ 的欧拉函数的值。也称作 $\Phi \ $函数。**
例 ： $\Phi (8) = 4$ ( $8$ 的互质数为 : $1,3,5,7$ )
特别地，$\Phi (1) = 1$
- 一些性质：
1. 若 $n$ 为质数则 $\Phi (n) = n-1$ .
2. 欧拉函数是积性函数——若 $m \perp n$，则 $\Phi (mn) = \Phi(m) \times \Phi(n) $。
3. 当 $n$ 为奇数时，$\Phi(2n) = \Phi(n)$ , 证明与上述类似。
4. 如果 $p$ 为质数 , 则有:
$\Phi (p^a) = p^a(1-\frac{1}{p})$
- 证明:
比 $p^a$ 小的数有 $p^a-1$ 个
其中与 $p^a$ 不互质的数 , 一定是 $p$ 的倍数
$p$ 的倍数可以这样表示 : $tp ,t \in [1\ ,\ p^{a-1}-1]$ , 故有 $p^{a-1}-1$ 个数
- 至于为什么 $\ \ t \in [1\ ,\ p^{a-1}-1]$ :
因为要保证列出的 $p$ 的倍数小于 $p^a$ ,
当 : $t=p^{a-1}$ 时 ，$tp=p^a$
则 : $0< t< p^{a-1}$
故 $\ \ t \in [1\ ,\ p^{a-1}-1]$
则与 $p$ 互质的数的个数为:
$\Phi (p^a)$
$=(p^a-1) - (p^{a-1}-1)$
$= p^a-p^{a-1}$
$=p^{a-1}(p-1)$
$= p^a(1-\frac{1}{p})$
5. 对于任意大于 $1$ 的正整数 $n$ ，有：
$\Phi (n) = n \times \prod\limits_{i=1}^{n} (1-\frac{1}{p_i}) $
- 证明:
先将 $n$ 进行质因数分解：
$n=P^{c1}_1\times P^{c2}_2 \times ...\times P^{cm}_m$
由性质 $4$ , 可得 :
$\Phi (p^{c1}_1) = p^{c1}_1(1-\frac{1}{p_1})$ , $\Phi (p^{c2}_2) = p^{c2}_2(1-\frac{1}{p_2})$
又因为性质 $2$ , 欧拉函数是积性函数 , 得:
$\Phi(n)$
$=\Phi(P^{c1}_1\times P^{c2}_2 \times ...\times P^{cm}_m)$
$=\Phi (p^{c1}_1)\times\Phi (p^{c2}_2)\times ... \times \Phi (p^{cm}_m)$
$=p^{c1}_1(1-\frac{1}{p_1})\times p^{c2}_2(1-\frac{1}{p_2})\times ...\times p^{cm}_m(1-\frac{1}{p_m})$
$=(p^{c1}_1\times p^{c2}_2\times ...\times p^{cm}_m)\times (1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})$
$=n \times \prod\limits_{i=1}^{n} (1-\frac{1}{p_i})$
原式得证 。
- 欧拉定理：
对于两个互质的数 $a$ 和 $p(p ≥ 2)$，有 $a ^{\Phi(p)} ≡ 1 \ \pmod p$ 。
- 证明：
设集合 $N=\{x_1,x_2,... ,x_{\Phi(p)}\}$ 为 $\Phi(p)$ 个小于 $p$ 且与 $p$ 互质的数,
$M=\{ax_1,ax_2,... ,ax_{\Phi(p)}\}$
**可证:** 任取$ax_s,ax_r \in M$ ,$\pmod p$ 下都不同余
- 子证明 ：
用反证法，假设：$ax_s \equiv ax_r \pmod p$
**则有 :**$(x_s-x_r)a=np \ (n\in Z)$
即: $p\mid (x_s-x_r)a$ ，
**但 :** $x_s,x_r<p$ , 则$(x_s-x_r)<p$
且 $a \perp p$ ,
**则 :** 与 $p\mid (x_s-x_r)a$ 相矛盾
故不成立，原式得证 。
**则 :** 集合 $M$ 中任意两元素 ， 在 $\pmod p$ 下，都不同余 。
则: $N=x_1 ,\ x_2\ ,\ ...\ ,\ x_{\Phi(p)}$,
在 $\pmod p$下，
与: $M=ax_1\ ,\ ax_2,\ ...\ ,\ ax_{\Phi(p)}$ 有映射相等关系 .
**则 :** $\large \prod\limits_{i\in N} \equiv \prod\limits_{j\in M} \pmod p$
**即 :**
$x_1\times\ ...\ \times x_{\Phi(p)} \equiv ax_1\times\ ...\ \times ax_{\Phi(p)} \pmod p$
$x_1\times\ ...\ \times x_{\Phi(p)} \equiv (x_1\times\ ...\ \times x_{\Phi(p)})a^{\Phi(p)} \pmod p$
同除 $x_1\times\ ...\ \times x_{\Phi(p)}$,得:
$a ^{\Phi(p)} ≡ 1 \ \pmod p$
**原式得证 。**
------------
本文为 @灵乌路空 @Luckyblock 原创
转载请联系作者,并注明出处
~~(虽然这么个小破文肯定不会有人转载的)~~