扩展欧几里得算法:
若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(){
int a,b,x,y,d;
cin>>a>>b;
d=exgcd(a,b,x,y);
cout<<a<<"*"<<x<<" + "<<b<<"*"<<y<<" = "<<d<<endl;
return 0;
}