扩展欧几里得算法
裴蜀定理:
- 若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。
换句话说:
- 两个整数a,b,方程
a*x+b*y=m
有解,当且仅当m是gcd(a,b)的倍数
思路
模版
// 求x, y,使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)//返回gcd(a,b)
{
if (!b)
{
x = 1; y = 0;
return a;
}
int gcd = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return gcd;
}
代码
#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y){//x,y引用带回,返回gcd(a,b)
if(b==0){
x=1,y=0;
return a;
}
int x1,y1,gcd;
gcd=exgcd(b,a%b,x1,y1);//递归调用
x=y1,y=x1-a/b*y1;
return gcd;
}
int main(){
int n;
cin>>n;
while(n--){
int a,b,x,y;
cin>>a>>b;
exgcd(a,b,x,y);
cout<<x<<' '<<y<<endl;
// cout<<exgcd(a,b,x,y)<<endl;//a,b的最大公约数
}
return 0;
}