欧几里得算法基本原理和证明
代码实现：
#include<iostream>
using namespace std;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int main(){
int x,y;
cin>>x>>y;
cout<<gcd(x,y)<<endl;
return 0;
}扩展欧几里得算法原理
代码实现：
#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
int res=exgcd(b,a%b,y,x);
y=y-(a/b)*x;
return res;
}
int main(){
int t;
cin>>t;
while(t--){
int a,b,x,y;
cin>>a>>b;
exgcd(a,b,x,y);
cout<<x<<" "<<y<<endl;
}
return 0;
}