Cod sursa(job #3183172)

Utilizator andiRTanasescu Andrei-Rares andiR Data 10 decembrie 2023 20:32:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");

int gcd(int a, int b){
    while (b!=0){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int lcm(int a, int b){
    return a*b/gcd(a, b);
}
int extgcd(int a, int b, int &ca1, int &cb1){
    ca1=1, cb1=0;
    int ca2=0, cb2=1, r, d;
    while (b!=0){
        r=a%b; d=a/b;
        a=b; b=r;
        ca1-=d*ca2; cb1-=d*cb2;
        swap(ca1, ca2); swap(cb1, cb2);
    }
    return a;
}

int main(){
    int n, a, b, c;
    fin>>n;
    while (n--){
        fin>>a>>b>>c;
        int x, y;
        int GCD=extgcd(a, b, x, y);
        if (c%GCD!=0)
            fout<<"0 0\n";
        else fout<<c/GCD*x<<' '<<c/GCD*y<<'\n';
    }
}