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

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

基本内容

求逆元

费马小定理求逆元，模数需要是质数。扩展欧几里得求逆元只需 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 提高组] 同余方程 - 洛谷

代码

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)

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';//最大}}   
}