数论-同余与扩展欧几里得详解(附例题及代码)
注意:这篇文章的信息量会有一点多，请耐心看完
(资料图片)
一.同余
1.1 同余的定义
给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)
简单来说，对于x,y，若x%p=y%p，即x,y对于p的余数相同，则称为同余
1.2 同余的性质
本身不重要，但我们可恶的教练让我们背下来
于是摆烂…………………………
实在是不想码出来(懒)
二.求解乘法逆元
2.1费马小定理(很费马)
2.1.1费马小定理简介
假设a是一个整数，p是一个质数，则有以下定理
\(a^{p-1}\)≡1(mod p)
证明方法：出门左转，百度（点击有惊喜）欢迎您
2.1.2费马小定理求解逆元
p为质数，则有\(a^{p-1}\)≡1(mod p)
则不难推出:\(a^{p-2}\)*a≡1(mod p)
所以，\(a^{p-2}\)就是a再在%p意义下的逆元
2.2欧拉定理
2.2.1欧拉定理简介
\(a^{φ(p)}\)≡1(mod p)(即为费马小定理的一般形式)
φ(p)为欧拉函数，不清楚的请出门左转见百度
2.2.2费马小定理求解逆元
推理:\(a^{φ(p)-1}\)*a≡1(mod p)
所以\(a^{φ(p)-1}\)就是a在%p意义下的逆元
2.2.3代码实现
long long ksm(long a,long p,long long mod){//快速幂 long long t=1,x=a%mod;while(p){if(p&1) t=t*x%mod;x=x*x%mod;p>>1;}return t; } long long getinv(long long a,long long mod){//inv一般表示逆元 return ksm(a,mod-2,mod); }2.3递推求解逆元(相信你十分了解递推)
2.3.1推理过程
p为模数，a为待求逆元(先设出来)，所以\(a^{-1}\)是a在模p意义下的逆元
p=k*a+r(k为常数，r为p/a的余数->r 则k=[p/a]，r=p%a k*a+r≡0 (mod p) 此时，两边同除ar，得 k*\(r^{-1}\)+\(a^{-1}\)≡0(mod p) \(a^{-1}\)≡-k*\(r^{-1}\)(mod p) inv(a)≡-[p/a]*inv(p%a) (mod p) 以inv(1)==1 作为边界，开始递推 说明了对任何整数a、b和它们的最大公约数d 关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数 特别地，一定存在整数x,y，使ax+by=d成立 它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1. 由此，我们便可对式子进行化简 将同余式ax≡c(mod b)转化为ax+by=c(很重要，做题列方程化简几乎必定会用到，牢记) 充分必要条件也即充要条件，意思是说，如果能从命题p推出命题q，而且也能从命题q推出命题p ，则称p是q的充分必要条件，且q也是p的充分必要条件。 样例： 1 A=“三角形的三条边都相等”；B=“三角形的三个角都相等”。 A是B的充分必要条件； 2 A=“某人触犯了法律”；B=“应当依照刑法对他处以刑罚”。 A是B的必要不充分条件；（A触犯法律包含各种法，有刑法有民法；B已经确定是刑法。B属于A所以A是B的必要不充分条件） 3 A=“付了足够的钱”；B=“买到商店里的东西”。 A是B的必要不充分条件；（ A付够了钱 可以买的是车、房子等；但是B能买到商店里的东西一定是要付够钱） ax1+by1=gcd(a,b) ax2+by2=gcd(a,b) 可由此推出 ax1+by1=ax2+by2 a(x1-x2)=b(y2-y1) 因为gcd(a,b)为a,b的最大公因数，所以将 A=a/gcd(a,b)，B=b/gcd(a,b)，向下推出 A(x1-x2)=B(y2-y1) 此时A，B互质，继续向下推出 A(nB)=B(nA) (x1-x2)=n*B (y2-y1)=n*A 重点部分 这里从x入手，得 (x1-x2)=n*B x1=x2+n*B 由此，我们推出了x解的通解公式 x=x0+n*B 同理，我们推出了y解的通解公式 y=y0-m*A 如果要求x的最小整数解,即x0,就为x0=x%B 如果我们要求的是 ax+by=c，还得先转化 x=x*c/gcd(a,b). 然后套入公式 B=b/gcd(a,b) x0=x%(b/gcd(a,b)) 证毕(博主已累成狗， (1).求解不定方程 (2).求解线性不定方程(线性同余方程) (3).求解模的逆元 思路:使用欧几里德扩展进行求解->模板题 代码如下 后续还会有数论的题解更新，敬请期待2.3.2代码实现
void getinv(long long mod){inv[1]=1;//边界条件for(int i=2;i2.4扩展欧几里得算法求逆元
2.4.1 前置知识-裴蜀定理(贝祖定理)
2.4.2小知识-充要条件
2.4.3扩展欧几里德算法—求最小整数解推导
点个推荐呗) 若还不清楚，可移步Ta的博客(讲的蛮详细的)2.4.4扩展欧几里德算法—代码实现
int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=1;return a;}int gcd=exgcd(b,a%b,y,x);//没错，这玩意能求gcd //不过c++是有系统函数求GCD的->__gcd(a,b);y-=a/b*x;return gcd; }2.4.4扩展欧几里德算法—应用场景
2.4.5扩展欧几里德算法—逆元求解
int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=1;return a;}int gcd=exgcd(b,a%b,y,x);y-=a/b*x;return gcd; } int getinv(int a,int p){int x,y,gcd;gcd=exgcd(a,p,x,y);if(gcd==1){x=(x%p+p)%p;return x;}else{cout<<"a,p不互质"<三.例题
3.1「NOIP2012」同余方程
#include
