扩展欧几里得算法
当$n$不为质数时的情况
扩展欧几里得算法,用于求$ax+by=\gcd(a,b)$的解
$\Rightarrow exgcd(a,b,x,y)$
那么,当$b==0$的时候,$ax+by=a \Rightarrow ax+b \times 0 =a$
$\Rightarrow ax=a$
$\Rightarrow x=1 ,y = 0$
当$b!=0$的时候,$ax+by=\gcd(a,b)= \gcd(b,a\%b)$
$$ \Rightarrow bx’ + (a\%b)y’=\gcd(b,a\%b) $$
$$ \Rightarrow bx’ + (a - \left \lfloor \frac{a}{b} \right \rfloor \times b)y’=\gcd(b,a\%b) $$
$$ \Rightarrow ay’ + b(x’ - \left \lfloor \frac{a}{b} \right \rfloor \times y’)=\gcd(b,a\%b)=\gcd(a,b) $$
所以说,可以得到的结果是$x=y’,y = x’ - \left \lfloor \frac{a}{b} \right \rfloor \times y’$
#include <iostream>
using namespace std;
int n;
void exgcd(int a,int b,int& x,int& y) {
if(!b) {
x = 1, y = 0;
return ;
}
int tx,ty;
exgcd(b,a % b,tx,ty);
x = ty, y = tx - a/b * ty;
}
int main() {
cin >> n;
while (n --) {
int a,b,x,y;
cin >> a >> b;
exgcd(a,b,x,y);
cout << x << " " << y << endl;
}
return 0;
}