扩展欧几里得算法
裴蜀定理
若有一对正整数a,b,那么一定存在正整数x,y使得ax+by=(a,b) => 即a和b能凑出来的最小的正整数
基本原理
$(a,b) = (b,a\%b)$
推导过程
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
//ax+by=gcd(a,b)的b为零的一个解
x=1,y=0;
return a;
}
//交换y与x的位置便于计算
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
cin>>n;
while (n -- ){
int a,b;
scanf("%d %d",&a,&b);
int x,y;
exgcd(a,b,x,y);
printf("%d %d",x,y);
cout<<endl;
}
}