[数论](5)扩展欧几里得
扩展欧几里得算法
裴蜀定理:有任意正整数a与b,存在x和y,使得ax+by=gcd(a,b)
伪码:
```C++ 在求解 gcd(a, b) 的过程中顺便求解两个系数x , y:
- 当 b == 0 时, 即 a x + 0 y = gcd(a, 0) = 0 即 x = 1, y = 0 即可!
- 当 b != 0 时:
由于:gcd(a, b) == gcd(b, a % b)
即:a x + b y = gcd(a, b) --> b y + a % b x = gcd(b, a % b)
(注:根据 x 与 y 的对应关系写出!) 由 a % b == a - a / b b,则该式变为:b y + (a - a / b b) x = gcd(b, a % b); 化简得:a x + b (y - a / b x) = gcd(b, a % b); 对应相等, 发现:x 没有变,y 减少了 a / b x:即 [ y -= a / b * x; ]
源码:
```C++ // 传入引用,随时更改值并返回! int exgcd(int a, int b, int & x, int & y){ if(b == 0){ // 1. 第一种情况: x = 1, y = 0; return a; } // 注意:这里y与x互换,是为了计算方便!不换也可以,用其他变量代替,化简完后根据对应相等再换回去即可! int t = exgcd(b, a % b, y, x); // 2. 第二种情况 y -= a / b * x; return t; }
**扩展欧几里得的应用 (求解线性同余方程)**

思路:

Ps:Bezout即是裴蜀定理
源码:
```C++
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int exgcd(int a,int b,int &x,int &y){//扩展欧几里得模板
if(b==0){
x=1;y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y= y - a / b * x;
return d;
}
int main(){
int n;
scanf("%d",&n);
while(n--){
int a,b,m;
scanf("%d %d %d",&a,&b,&m);
int x,y;
int d=exgcd(a,m,x,y);
if(b%d) printf("impossible\n");
else printf("%lld\n",(long long)x*(b/d)%m);
}
return 0;
}
扩展欧几里得的应用(求乘法逆元)
当n不是质数时,可以用扩展欧几里得算法求逆元: a有逆元的充要条件是a与p互质,所以gcd(a, p) = 1 假设a的逆元为x,那么有a * x ≡ 1 (mod p) 等价:ax + py = 1 逆元 = exgcd(a, p, x, y)