current position:Home>Mathematical knowledge: extended Euclidean algorithm - extended Euclidean algorithm

Mathematical knowledge: extended Euclidean algorithm - extended Euclidean algorithm

2022-06-24 09:04:58Fight! Sao Nian!

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;
}

copyright notice
author[Fight! Sao Nian!],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/175/202206240712128328.html

Random recommended