基础数论总结
GCD&LCM
辗转相除求gcd
$gcd(x,y)=gcd(y,x\%y)$ ,易证。
1 | int gcd(int x,int y) |
求lcm
证明:
设 $x=p\times a$ , $y=p \times b$ 且$gcd(a,b)=1$
则有 $gcd(x,y)=p,lcm(x,y)=lcm(a,b)\times p$
$a,b$ 互质 ,故 $lcm(a,b)=a\times b ,lcm(x,y)=a\times b\times p$
证毕
扩展欧几里德 ExGCD
用于求方程 $ax+by=gcd(a,b)$ 的一组解
1 | int exgcd(int x,int y,int &a,int &b) |
- 注意:代码里的 $x,y,a,b$ 与我所述的是反的
证明:
在 $ax+by=gcd(a,b)$ 中,
当 $b=0$ 时,
显然为方程的一组合法解。
已知 $bx+(a\%b)y=gcd(b,a\%b)$ 的解,考虑向 $ax’+by’=gcd(a,b)$ 的解转移
由于
所以可得方程
显然一组可行解为
证毕
ExGCD求$ax+by=1$
用ExGCD解出$ax’+by’=gcd(a,b)$的一组解后
由
可得
求得$ax+by=1$的一组解后,可由一组解扩展出所有解
显然
则
为$ax+by=1$的解的通项
费马小定理
如果$p$是质数,且$a$与$p$互质,则有:
欧拉定理
乘法逆元
定义
如果 $ab\equiv 1(mod\;p)$ ,则 $a,b$ 互为 $mod\;p$ 意义下的乘法逆元
说明:众所周知,除法是不可膜的。而乘法逆元是为了使除法可膜而诞生的。
即$ \dfrac a b\equiv a\times inv(b)(mod\;p)$,其中$a$为任意整数。
化简可得,$b\times inv(b)\equiv1(mod\;p)$
求法
费马小定理
可用于解决膜数$p$为质数的情况
则$a^{p-2}$即为$a\;mod\;p$意义下的逆元,快速幂可求
欧拉定理
可用于解决膜数$p$不为质数的情况
则$a^{\varphi(p)-1}$即为$a\;mod\;p$意义下的逆元,快速幂可求
ExGCD
由
可得
Exgcd可求得解
顺便记录一下自己的智障问题:这样不是会求出很多解吗?
答:$inv(a)$的所有解都是$inv(a)+k\times p$,$mod\;p$之后都是一样的
线性递推
证明:
设$A=\lfloor\dfrac p i\rfloor,B=p\%i$,则$A\times i+B=p$。
则有
即
阶乘逆元
可以$O(n)$求出$1!\cdots n!$的逆元,组合数常用
则
可以先求出$inv(a!)$,然后推出所有阶乘的逆元
中国剩余定理 CRT
设$m_1,m_2,\ldots,m_k$两两互素,则同余方程组
有整数解;
并且在$mod\;M=\prod_{i=1}^{k}m_i$意义下有唯一解,为
其中$M_i=\dfrac{M}{m_i}$,$inv(M_i)$为$M_i\;mod\;m_i$意义下的逆元
扩展中国剩余定理 exCRT
解同余方程
假设我们已经解出了前 $k-1$ 组解 $x_{k-1}$,那么 $x_k$ 一定为 $x_{k-1}+t\times LCM(m_1,m_2,\cdots m_{k-1})$。
则有
用 exgcd 解同余方程即可。