欧几里得 ---＞ 裴蜀定理 ---＞ 拓展欧几里得

欧几里得 —> 裴蜀定理 —> 拓展欧几里得

基本内容

求逆元

费马小定理求逆元，模数需要是质数。扩展欧几里得求逆元只需 a 与 m 互质

证明

欧几里得算法（辗转相除法）

核心定理：对于任意整数 (a, b)$(a\ge b\ge 0)$，有 $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$。
证明步骤：

1. 余数性质：设 (a = bq + r)（其中 $r=a\mathrm{mod}b$)，则 (a) 和 (b) 的公约数必然也是 (b) 和 (r) 的公约数，反之亦然。
   • 若 $d\mid a$ 且 $d\mid b$，则 $ d \mid (a - bq) = r$。
   • 若$d\mid b$ 且 $d\mid r$，则 $ d \mid (bq + r) = a$。
2. 数学归纳法：
   • 基例：当 (b = 0) 时，(\gcd(a, 0) = a)，显然成立。
   • 归纳假设：假设对 (b < k) 时定理成立。
   • 归纳步骤：当 (b = k) 时，通过余数 (r = a \bmod b) 递归缩小问题规模，最终余数为零时，非零余数即为 GCD。
     应用场景：快速计算两个数的最大公约数，例如分数约分、素数检测等。

内容引用自：董晓 - 博客园

裴蜀定理

扩展欧几里得定理

1. 求不定方程 $ax+by=gcd（a,b）$
2. 求解同余方程
3. 求解乘法逆元

时间复杂度：O(log n)

void exgcd(int a,int b)
{
	if(b==0)
	{
		x=1,y=0;
		return ;
	}
    exgcd(b,a%b);
	int te=x;
	x=y;y=te-a/b*y;
	return ;
} 

题目运用

裴蜀定理

P4549 【模板】裴蜀定理 - 洛谷

代码

int a[N];
void solve()
{
	int n,s=0;
	cin>>n;
	fir(i,1,n)   
	{
		cin>>a[i];
		s=__gcd(s,abs(a[i]));
	}         
	cout<<s<<'\n';
}

扩展欧几里得

[P1082 NOIP 2012 提高组] 同余方程 - 洛谷

x%y= x-(x/y) * y

对 b 取模，可以看作 **+b y ** (y为负值)

所以式子可以转化为

ax+by=1

求 x 的解。

代码

int x,y,a,b;
void exgcd(int a,int b)
{
	if(b==0)
	{
		x=1,y=0;
		return ;
	}
 
    exgcd(b,a%b);
	int te=x;
	x=y;y=te-a/b*y;
	return ;
}
void solve()
{
	cin>>a>>b;
 	exgcd(a,b);
 	x=(x%b+b)%b;
	cout<<x<<'\n';
}

P5656 【模板】二元一次不定方程 (exgcd)

题目：判断 ax+by =c 的解

• c ! = gcd(a,b) 无解
• 用加减 p ， q 求通解

int a,b,c,x,y;
void exgcd(int a,int b)
{
	if(b==0)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	int t=x;
	x=y,y=t-a/b*y;
	return;
}
void solve()
{
	x=0,y=0;
	cin>>a>>b>>c;
	if(c%__gcd(a,b)!=0) 
	cout<<"-1\n";
	else 
	{
		exgcd(a,b);
		int d=a*x+b*y;//公因数
		x*=c/d,y*=c/d;//
		int p=b/d,q=a/d;
		if(x<=0)
		{
			int k=(1-x+p-1)/p;
			x+=k*p;
			y-=k*q;
		}
		else 
		{
			int k=(x-1)/p;
			x-=k*p;
			y+=k*q;
		}
		if(y<=0) 
		{
			int k=(1-y+q-1)/q;
			y+=k*q;
			cout<<x<<' '<<y<<'\n';//x,y最小正整数解
		}
		else
		{
			cout<<(y-1)/q+1<<' ';        //y减到1的方案数为解的个数
			cout<<x<<' '<<(y-1)%q+1<<' ';//最小
			cout<<x+(y-1)/q*p<<' '<<y<<'\n';//最大
		}
	}   
}