同余学习笔记
定义
若整数 $a$ 和整数 $b$ 除以正整数 $m$ 的余数相等，则称 $a,b$ 模 $m$ 同余，记为 $a\equiv b\ (mod\ m)$ 。
同余系与剩余系
对于 $\forall a\in[0,m-1]$ ，集合 {$a+km$} $(k\in\N)$ 的所有数模 $m$ 同余，余数都是 $a$ 。该集合称为一个模 $m$ 的同余类，简记为 $\bar{a}$ 。
模 $m$ 的同余类一共有 $m$ 个，分别为 $\bar{0},\bar{1},\cdots,\overline{m-1}$ 。它们构成 $m$ 的完全剩余系。
$1\sim m$ 中与 $m$ 互质的数代表的同余类共有 $\varphi(m)$ 个，它们构成 $m$ 的简化剩余系。
简化剩余系关于模 $m$ 乘法封闭。这是因为若 $a,b(1\leq a,b\leq m)$ 与 $m$ 互质，则 $ab$ 也不可能与 $m$ 有相同的质因子，即 $gcd(ab,m)=1$ 。再由余数的定义可知 $ab\ mod\ m$ 也与 $m$ 互质，即 $ab\ mod\ m$ 也属于 $m$ 的简化剩余系。
欧拉定理
费马小定理
若 $p$ 是质数，则对于任意整数 $a$ ，有 $a^p\equiv a\ (mod\ p)$ 。
欧拉定理
若正整数 $a,n$ 互质，则 $a^{\varphi(n)}\equiv 1\ (mod\ n)$ 。
证明：
设 $n$ 的简化剩余系为 {$\overline{a_1},\overline{a_2},\cdots,\overline{a_{\varphi(n)}}$}。对 $\forall a_i,a_j$ ，若 $aa_i\equiv aa_j\ (mod\ n)$ ，则 $a*(a_i-a_j)\equiv 0$ 。因为 $a,n$ 互质，所以 $a_i-a_j\equiv 0$ ，即 $a_i\equiv a_j$ 。故当 $a_i\not= a_j$ 时， $aa_i,aa_j$ 也代表不同的同余类。
又因为简化同余系关于模 $n$ 乘法封闭，故 $\overline{aa_i}$ 也在简化剩余系中。因此，集合 {$\overline{a_1},\overline{a_2},\cdots,\overline{a_{\varphi(n)}}$}与集合 {$\overline{aa_1},\overline{aa_2},\cdots,\overline{aa_{\varphi(n)}}$}都能表示 $n$ 的简化剩余系。综上所述： $a^{\varphi(n)}a_1a_2\cdots a_{\varphi(n)}\equiv(aa_1)(aa_2)\cdots(aa_{\varphi(n)})\equiv a_1a_2\cdots a_{\varphi(n)}\ (mod\ n)$
因此 $a^{\varphi(n)}\equiv1\ (mod\ n)$ 。
当 $p$ 是质数时， $\varphi(n)=n-1$ ，并且只有 $p$ 的倍数与 $p$ 不互质。所以，只要 $a$ 不是 $p$ 的倍数，就有 $a^{p-1}\equiv1\ (mod\ p)$ ，两边同乘 $a$ 就是费马小定理。另外，若 $a$ 是 $p$ 的倍数，费马小定理显然成立。
证毕。
欧拉定理的推论
若正整数 $a,n$ 互质，则对于任意正整数 $b$ ，有 $a^b\equiv a^{b\ (mod\ \varphi(n))}\ (mod\ n)$ 。
对于一些计数类题目，如果要计算乘方算式，根据欧拉定理，可以先把底数对 $p$ 取模、指数对 $\varphi(n)$ 取模。再计算乘方。
特别的，当 $a,n$ 不一定互质且 $b>\varphi(n)$ 时，有 $a^b\equiv a^{b\ mod\ \varphi(n)+\varphi(n)}\ (mod\ n)$ 。这意味着即使底数和模数不互质，我们也有办法把指数的规模缩小到容易计算的范围内。上式可以通过寻找 $a^b\ mod\ n$ 的指数循环节证明。
例题
题面
Solution
$x$ 个 $8$ 连在一起组成的正整数可以写成 $8(10^x-1)/9$ 。题目要求一个最小的 $x$ 满足 $L|8(10^x-1)/9$ 。
设 $gcd(8,L)=d$ ，则 $\frac{L}{d}|\frac{8}{d}(10^x-1)/9$ 。由于 $\frac{L}{8}$ 与 $\frac{8}{d}$ 互质，所以 $\frac{L}{d}|(10^x-1)/9$ 。整理得到 $\frac{9L}{d}|10^x-1$ 。写成同余的形式 $10^x\equiv 1\ (mod\ \frac{9L}{d})$ 。
写到这里我们想到欧拉定理的形式。
- 对于 $gcd(10,\frac{9L}{d})!=1$ ，方程无解。
证明：以上方程等价于 $10^x=m\frac{9L}{d}+1$ ，所以 $gcd(10^x,\frac{9l}{d})=gcd(m\frac{9l}{d}+1,\frac{9l}{d})=gcd(1,\frac{9l}{d})=1$ 。
- 若 $a,n$ 互质，则满足 $a^x\equiv 1\ (mod\ n)$ 的最小正整数解 $x_0$ 一定是 $\varphi(n)$ 的约数。
证明：假设 $x_0\not|\ \varphi(n)$ ，则 $\varphi(n)=mx_0+r\ (0<r<x_0)$ 。因为 $a^{\varphi(n)}\equiv 1\ (mod\ n)$ ，那么 $a^{mx_0+r}\equiv 1\ (mod\ n)$ 。因为 $a^{x_0}\equiv 1\ (mod\ n)$ ，那么对上式化简得 $a^r\equiv 1\ (mod\ n)$ 。这与 $x_0$ 最小矛盾，假设不成立。原命题成立。
因此我们只需要求出 $\varphi(\frac{9l}{d})$ ，然后枚举它的约数，用快速幂判断即可。
时间复杂度： $o(\sqrt{L}\ log\ L)$ 。
Code
1 |
|
拓展欧几里得算法
Bezout定理
对于任意整数 $a,b$ ，一定存在一对整数 $x,y$ 满足 $ax+by=gcd(a,b)$ 。
证明：
在欧几里得算法的最后一步，即 $b=0$ 时，显然有一对整数 $x=1,y=0$ ，使得 $a1+00=gcd(a,0)$ 。
若 $b>0$ ，则 $gcd(a,b)=gcd(b,a\%b)$ 。
假设存在一对整数 $x,y$ ，满足 $bx+(a\%b)y=gcd(b,a\%b)$ 。
因为 $bx+(a\%b)y=bx+(a-b\lfloor a/b\rfloor)y=ay+b(x-\lfloor a/b\rfloor y)$ ，所以令 $x^{‘}=y,y^{‘}=x-\lfloor a/b\rfloor y$ ，就得到了 $ax^{‘}+by^{‘}=gcd(a,b)$ 。
对欧几里得算法的递归过程应用数学归纳法，可知定理成立。
Bezout定理是按照欧几里得算法的思路证明的，且上述证明的同时给出了整数 $x,y$ 的计算方法。这种计算方法被称作拓展欧几里得算法。
1 | int exgcd(int a,int b,int &x,int &y){ |
上述程序求出方程 $ax+by=gcd(a,b)$ 的一组特解 $x_0,y_0$ ，并返回 $a,b$ 的最大公约数 $d$ 。
对于更一般的方程 $ax+by=c$ ，它有解当且仅当 $d|c,d=gcd(a,b)$ 。我们可以先求出 $ax+by=d$ 的一组特解 $x_0,y_0$ ，然后令 $x_0,y_0$ 同时乘上 $\frac{c}{d}$ ，就得到了 $ax+by=c$ 的一组特解 $\frac{c}{d}x_0,\frac{c}{d}y_0$ 。
事实上，方程 $ax+by=c$ 的通解可以表示为： $x=\frac{c}{d}x_0+k\frac{b}{d},y=\frac{c}{d}y_0+k\frac{a}{d},k\in\N$ 。
例题
题面
Solution
假设要跳 $x$ 次才能相遇，则题目等价于求一个最小的 $x$ ，使得 $a+nx\equiv b+mx\ (mod\ L)$ 。
整理式子。
$(n-m)x\equiv b-a\ (mod\ L)$
将同余号去掉，得 $x(n-m)+kL=b-a$ 。其中 $n-m,L,b-a$ 均为已知量，所以可以用 $exgcd$ 求解。
注意到 $n-m$ 的符号不确定，所以在做题之前进行一下处理，先将 $n-m$ 变为正数，再将 $b-a$ 变为正数，最后再转换为二元一次方程求解。（注意要开 $long\ long$ ）
Code
1 |
|
乘法逆元
若整数 $b,m$ 互质，并且 $b|a$ ，则存在一个整数 $x$ ，使得 $a/b\equiv ax\ (mod\ m)$ 。称*$x$ 为 $b$ 的模 $m$ 的乘法逆元。记为 $b^{-1}(mod\ m)$ 。
因为 $a/b\equiv ab^{-1}\equiv a/bbb^{-1}(mod\ m)$ ，所以 $bb^{-1}\equiv 1(mod\ m)$ 。
如果 $m$ 为质数（此时用 $p$ 代替 $m$ ），并且 $b<p$ ，根据费马小定理， $b^{p-1}\equiv1(mod\ p)$ ，即 $bb^{p-2}\equiv1(mod\ p)$ 。因此，*当模数 $p$ 为质数时， $b^{p-2}$ 即为 $b$ 的乘法逆元。
如果只是保证 $b,m$ 互质，那么乘法逆元可通过求解同余方程 $b*x\equiv 1(mod\ m)$得到
运用乘法逆元，我们在计数类问题中遇到 $a/b$ 这样的除法算式，也可以先把 $a,b$ 各自对模数 $p$ 取模，再计算 $a*b^{-1}(mod\ p)$ 作为最终结果。当然，前提是必须保证 $b,p$ 互质。
线性同余方程
给定正数 $a,b,m$ ，求一个整数 $x$ 满足 $a*x\equiv b(mod\ m)$ ，或者给出无解。因为未知数的指数为 $1$ ，所以我们称之为一次同余方程，也称为线性同余方程。
$ax\equiv b(mod\ m)$ 等价于 $ax-b$ 是 $m$ 的倍数，不放设为 $-y$ 倍。于是该方程可以改写为 $ax+my=b$ 。
线性同余方程有解当且仅当 $gcd(a,m)|b$ 。
中国剩余定理
设 $m_1,m_2,\cdots,m_n$ 是两两互质的整数， $m=\prod\limits_{i=1}^n m_i$ ， $M_i=m/m_i$ ， $t_i$ 是线性同余方程 $M_it_i\equiv 1(mod\ m_i)$ 的一个解。对于任意的 $n$ 个整数 $a_1,a_2,\cdots,a_n$ ，方程组 $\left\{\begin{matrix}
x\equiv a_1(mod\ m_1)\\
x\equiv a_2(mod\ m_2)\\
\cdots\\
x\equiv a_2(mod\ m_3)\\
\end{matrix}\right.$ 有整数解，解为 $x=\sum\limits_{i=1}^n a_i M_i t_i$ 。
证明：
因为 $M_i=M/m_i$ ，是除 $m_i$ 外所有模数的倍数，所以 $\forall k\not= i,a_i M_i t_i\equiv 0(mod\ m_k)$ 。又因为 $a_iM_it_i\equiv a_i(mod\ m_i)$ ，所以带入 $x=\sum\limits_{i=1}^n a_i M_i t_i$ ，原方程组成立。
拓展中国剩余定理
已知方程组 $\left\{\begin{matrix}
x\equiv a_1(mod\ m_1)\\
x\equiv a_2(mod\ m_2)\\
\cdots\\
x\equiv a_2(mod\ m_3)\\
\end{matrix}\right.$ ，求一个最小的 $x$ 使得 $\forall i\in [1,n],x\equiv a_i\ (mod\ m_i)$ ，或给出无解。
假设前 $k-1$ 个方程求出的解为 $x$ 。记 $m=lcm(m_1,m_2,\cdots,m_{k-1})$ 。
则 $x+i*m,i\in\Z$ 是前 $k-1$ 个方程的通解。
考虑第 $k$ 个方程，求出一个 $t$ ，使得 $x+t*m\equiv a_k\ (mod\ m_k)$ 。明显，这是一个线性同余方程，可以用拓欧判断有解。
若有解，则 $x^{‘}=x+t*m$ 是前 $k$ 个方程的一个解。
综上所述，我们使用 $n$ 次拓欧即可算出整个方程的解。
例题
Code
1 |
|
高次同余方程
高次同余方程，有 $a^x\equiv b\ (mod\ p)$ 和 $x^a\equiv b\ (mod\ p)$ 两类。
Baby Step,Giant Step 算法
问题：
给定整数 $a,b,p$ ，其中 $a,p$ 互质。求一个非负整数 $x$ ，使得 $a^x\equiv b\ (mod\ p)$ 。
因为 $a,p$ 互质，所以可以在模 $p$ 意义下执行关于 $a$ 的乘除运算。
设 $x=it-j$ ，其中 $t=\lceil \sqrt{p}\ \ \rceil,0\leq j\leq t-1$ 。则方程变为 $a^{it-j}\equiv b\ (mod\ p)$ 。即 $(a^t)^i\equiv b*a^j\ (mod\ p)$ 。
对于所有的 $j\in[0,t-1]$ ，把 $b*a^j\ mod\ p$ 的值插入一个 $hash$ 表。
枚举 $i$ 的所有取值，即 $i\in[0,t]$ ，计算出 $(a^t)^i\ mod\ p$ ，在 $hash$ 表里查找是否存在对应的 $j$ ，更新答案即可。时间复杂度： $O(\sqrt{p})$ 。
例题
Solution
对于 $111\cdots 111$ 这种形式，我们可以套路性的拆分一下： $111\cdots 111=\frac{10^n-1}{9}$ 。
这样原式就化成了 $\frac{10^n-1}{9}\equiv k\ (mod\ m)$ 。
再变一下，可以得到 $10^n\equiv 9k+1\ (mod\ m)$ 。
因为 $m$ 是一个质数，所以 $gcd(10,m)=1$ ，可以用 $BSGS$ 解决。
Code
1 |
|
拓展 $BSGS$ 算法
问题：
给定整数 $a,b,p$ 。求一个非负整数 $x$ ，使得 $a^x\equiv b\ (mod\ p)$ 。
当 $gcd(a,p)\not |\ b,b\not= 1$ 时，原方程无解。
设 $d=gcd(a,p)$ 。我们可以将所有的数同时除以 $d$ 。
这时，方程变成了： $a^{x-1}*\frac{a}{d}\equiv \frac{b}{d}\ (mod\ \frac{p}{d})$ 。
设 $g=\frac{d}{a}$ ，则 $a^{x-1}\equiv b*g\ (mod\ \frac{p}{d})$ 。
令 $x^{‘}=x-1,b^{‘}=b*g,p^{‘}=\frac{p}{d}$ ，可得到一个新的方程。
然后继续递归解决，直到到一定规模后暴力求解，或出现质数时用 $BSGS$ 。
例题
Code
1 |
|