Mathematical knowledge: extended Euclidean algorithm - extended Euclidean algorithm

2022-06-24 09:04:58

subject ：AcWing 877. extended euclidean algorithm
Given n Right integer ai,bi, For each logarithm , Find a set of xi,yi, To make it meet the ai×xi+bi×yi=gcd(ai,bi).

Input format
The first line contains integers n.

Next n That's ok , Each line contains two integers ai,bi.

Output format
The output, n That's ok , For each group ai,bi, Find a set of xi,yi, Each group has one line .

The answer to this question is not unique , Output any condition satisfied xi,yi All possible .

Data range
1≤n≤105,
1≤ai,bi≤2×109

sample input ：

2
4 6
8 18

sample output ：

-1 1
-2 1

``````#include <iostream>

using namespace std;
int exgcd(int a,int b,int &x,int &y)
{

if(!b)//  If b by 0, be a*1+b*0=a;
{

x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y -= a/b*x;
return d;
}
int main()
{

int n;
cin>>n;
int a,b;
while(n--)
{

cin>>a>>b;
int x,y;
exgcd(a,b,x,y);
cout<<x<<' '<<y<<endl;
}
return 0;
}
``````