Cod sursa(job #2784841)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 17 octombrie 2021 15:08:58
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>
#define LL long long

using namespace std;

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

long long teste, a, b, c, d, xsol, ysol;

LL euclid_extins(LL a, LL b, LL &x, LL &y){
    if(b == 0){ x=1; y=0; return a;}
    LL nxtX, nxtY, rest;

    rest=euclid_extins(b, a%b, nxtX, nxtY);

    x=nxtY;
    y=nxtX - nxtY * (a/b);

    return rest;
}

int main (){
    fin>>teste;
    while(teste--){
        fin>>a>>b>>c;
        d = euclid_extins(a, b, xsol, ysol);
        if(c%d != 0)
            fout<<"0 0";
        else
            fout<<c/d * xsol<<" "<<c/d * ysol;
        fout<<"\n";
    }
    return 0;
}