数论-同余与扩展欧几里得详解(附例题及代码)

注意:这篇文章的信息量会有一点多，请耐心看完

一.同余

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<a(易得))

则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 作为边界，开始递推

2.3.2代码实现

  void getinv(long long mod){
	inv[1]=1;//边界条件
	for(int i=2;i<mod;i++){
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;//递推核心代码
	}
  }

2.4扩展欧几里得算法求逆元

2.4.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(很重要，做题列方程化简几乎必定会用到，牢记)

2.4.2小知识-充要条件

充分必要条件也即充要条件，意思是说，如果能从命题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能买到商店里的东西一定是要付够钱）

2.4.3扩展欧几里德算法—求最小整数解推导

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))

证毕(博主已累成狗，点个推荐呗) 若还不清楚，可移步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扩展欧几里德算法—应用场景

(1).求解不定方程

(2).求解线性不定方程(线性同余方程)

(3).求解模的逆元

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不互质"<<endl;
		return 0; 
	}
  }

三.例题

3.1「NOIP2012」同余方程

思路:使用欧几里德扩展进行求解->模板题

代码如下

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  int x=0,y=0;
  int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int g=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return g;
  }
  signed main(){
	int a,b;
	cin>>a>>b;
	exgcd(a,b,x,y);
	cout<<(x%b+b)%b;
	return 0;
  }

后续还会有数论的题解更新，敬请期待