partychicken
Articles12
Tags3
Categories3
基础数论总结

基础数论总结

GCD&LCM

辗转相除求gcd

$gcd(x,y)=gcd(y,x\%y)$ ,易证。

1
2
3
4
5
int gcd(int x,int y)
{
if(!y) return x;
return gcd(y,x%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
2
3
4
5
6
7
8
9
10
11
12
13
14
int exgcd(int x,int y,int &a,int &b)
{
if(!y)
{
a=1;
b=0;
return x;
}
int res=exgcd(y,x%y,a,b);
int tmp=a;
a=b;
b=tmp-(x/y)*b;
return res;
}
  • 注意:代码里的 $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 解同余方程即可。

扩展欧拉定理

Author:partychicken
Link:http://partychicken.github.io/2022/04/20/%E6%95%B0%E8%AE%BA/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
×