欧几里德算法(gcd)

辗转相除,求最小公因数
定理

gcd(a,b)=gcd(b,a%b);

gcd(a,0)=0;
证明(假设a>b)
充分性

将a写成 a=k*b+r; 设d为a,b的一个公因数,则d|a,d|b

而r=a-k*b

r/d=a/d-k*b/d 由假设可知右侧为正整数显然d|r

得证
必要性

设d|a,d|(a%b)

显然d|(a-k*b) (k为整数)

显然d|a 得证
拓展欧几里德算法

在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a,b) = d（解一定存在，根据数论中的相关定理）。扩展欧几里德常

用在求解模线性方程及方程组中。(依赖于欧几里德算法)
贝祖等式

在数论中，裴蜀等式（英语：Bézout’s identity）或贝祖定理（Bézout’s lemma）是一个关于最大公约数（或最大公约式）的定理。

裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程（称为裴蜀等

式）：

ax + by = gcd(a,b) = d 有整数解时当且仅当m是d的倍数。

裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用扩展欧几里得算法(Extended Euclidean algorithm)求得。

特别来说，方程 ax+by=1 有整数解当且仅当整数a和b互素。

裴蜀等式也可以用来给最大公约数定义： d其实就是最小的可以写成ax+by形式的正整数。(这个定义的本质是整环中“理想”的概念。因

此对于多项式整环也有相应的裴蜀定理。)
证明:

如果 a 和 b 中有一个是 0，比如 a=0，那么它们两个的最大公约数是 b。这时裴蜀等式变成 by=d，它有整数解 (x,y) 当且仅当 d

是 b 的倍数，而且有解时必然有无穷多个解，因为 x 可以是任何整数。定理成立。

以下设 a和 b 都不为0。

设 A={xa+yb;(x,y)∈Z2} ，下面证明A中的最小正元素是 a 与 b 的最大公约数。

首先，A∩N∗ 不是空集（至少包含|a| 和|b|），因此由于自然数集合是良序的， A 中存在最小正元素d0=x0a+y0b。考虑A中任意一个正

元素p（=x1a+y1b）对 d0 的带余除法：设p=qd0+r，其中 q 为正整数，0≤r<d0。但是

r=p−qd0=x1a+y1b−q(x0a+y0b)∈A

而d0 已经是集合 A 中最小的正元素了，又 0≤r<d0,所以 r=0。

因此 d0 | p。也就是说，A中任意一个正元素p都是 d0 的倍数，特别地：d0 | a、d0 | b。因此 d0 是 a 和 b 的公约数。

另一方面，对 a 和 b 的任意正公约数d，设 a=kd、b=ld，那么

d0=x0a+y0b=(x0k+y0l)d

x0k+y0l≥1 ,因此 d | d0。所以 d0 是 a 和 b 的最大公约数。

在方程ax+by=m中，如果 m=m0d0，那么方程显然有无穷多个解

相反的，如果ax+by=m有整数解，那么 |m|∈A，于是由前可知 d0 | |m|（即 d0 | m）。

m=1时，方程有解当且仅当a、b互质。
拓展欧几里德算法

扩展欧几里德算法就是在求 a,b 的最大公约数 m=gcd(a,b) 的同时，求出贝祖等式ax + by = m的一个解 (x,y)。

有两个数 a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以

得到 ax+by=gcd(a,b)的整数解。
先来看下这个几乎所有总结扩展欧几里德算法的帖子中都会用到的例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
用类似辗转相除法，求二元一次不定方程47x+30y=1的整数解。
47=30*1+17
30=17*1+13
17=13*1+4
13=4*3+1
然后把它们改写成“余数等于”的形式

17=47*1+30*(-1) //式1
13=30*1+17*(-1) //式2
4=17*1+13*(-1) //式3
1=13*1+4*(-3)
然后把它们“倒回去”

1=13*1+4*(-3) //应用式3
1=13*1+[17*1+13*(-1)]*(-3)
1=13*4+17*(-3) //应用式2
1=[30*1+17*(-1)]*4+17*(-3)
1=30*4+17*(-7) //应用式1
1=30*4+[47*1+30*(-1)]*(-7)
1=30*11+47*(-7)
得解x=-7, y=11。
现在的问题就是找到这个倒推回去的递推式
1
2
3
4
5
6
7
8
9
10
11
12
13
 设：a>b。
　　推理1，显然当 b=0，gcd（a，b）=a。
 此时 x=1，y=0;//推理1
　　推理2，ab!=0 时
　　设 ax1+by1=gcd(a,b);
　　bx2+(a mod b)y2=gcd(b,a mod b);
　　根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
　　则:ax1+by1=bx2+(a mod b)y2;
　　即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
　　根据恒等定理得：x1=y2 ,y1=x2-(a/b)*y2;//推理2
　　这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是以递归定义的
因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。
然后我们就找到了递推式

x1=y2;

y1=x2−(a/b)∗y2;

当b=0，gcd（a，b）=a。此时x=1，y=0;(终止条件)
于是我们得到了拓展欧几里德算法的代码
1
2
3
4
5
6
7
inline void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1; y=0;}
    else {
        exgcd(b,a%b,x,y); 
        ll t=x;x=y;y=t-a/b*x;
    }
}

乘法逆元

若ax≡1 mod m, 则称a关于1模m的乘法逆元为x。也可表示为ax≡1(mod m)。

如果a,m不互质，则无解。如果m为质数，则从1到m−1的任意数都与m互质，即在1到m−1之间都恰好有一个关于模m的乘法逆元。
求法

欧拉定理

欧拉定理： $a^{φ(m)}$ ≡1(mod m) (φ(m)是小于m且与m互质的数的个数。)

变形得: $a^{aφ(m)−1}$ ≡1(mod m)

故 $a^{φ(m)−1}$ 为a在模m下的逆元。( $a^{φ(m)−1}$ 用快速幂求解即可)
费马小定理

假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p），例如：假如a是整数，p是质数，则a,p显然互质(即两者只有一个公约数1)，

那么我们可以得到费马小定理的一个特例，即当p为质数时候， a^(p-1)≡1(mod p)。

则a*a^(p-2)≡1(mod p) 显然a^(p-2)就是a关于%p的逆元

费马小定理实质上是欧拉定理的一个特殊情况
拓展欧几里德

详情看上面，但是注意求出来的逆元可能为负数，只需要加上p再%p就好
斯特林公式

斯特林公式是一条用来取n的阶乘的近似值的数学公式。一般来说，当n很大的时候，n阶乘的计算量十分大，所以斯特林公式十分好用，

而且，即使在n很小的时候，斯特林公式的取值已经十分准确。
$n!\approx\sqrt{2\pi n}(\frac{n}{e})^n$

lucas定理

Lucas定理是用来求 C(n,m)mod p，p为素数的值。

适用领域范围：大组合数求模,n,m>p
$C_n^m \%p=C_{n/p}^{m/p}*C_{n \%p}^{n \%m}\ %p$

线性求逆元

有时我们需要1~p所有元素的逆元，当p很大的时候常规的求逆元方式的时间复杂度都比较高最快也是O(p*log(p))

只需要一点简单的推倒，我们就可以O(p)地求解

先给出递推式
inv[i]=(p-p/i)*inv[p%i]%p

推导

设 t=p/i,k=p%i,那么

t*i+k≡0(mod p)

-ti≡k(mod p) 两边同除ik

得到

-t*inv[k]≡invi

替换回去可以得到

inv[i]=(p-p/i)*inv[p%i]%p

初始化inv[1]=1 就可以递推地求解了
判断组合数奇偶

$C_n^m$ 为奇数时n%m==m