Cod sursa(job #3153724)

Utilizator GrigMihaiGrigore Mihai GrigMihai Data 30 septembrie 2023 22:16:26
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>

using namespace std;

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

int gcd_ext(int a, int b, int& x, int&y)
{
    int xa=1, ya=0, xb=0, yb=1;

    while(a%b!=0)
    {
        int aux1, aux2;
        aux1=xb;
        aux2=yb;

        xb=xa-aux1*(a/b);
        yb=ya-aux2*(a/b);

        xa=aux1;
        ya=aux2;

        aux1=b;
        b=a%b;
        a=aux1;
    }

    x=xb;
    y=yb;
    return b;
}

int main() {

    int t;

    in>>t;

    while(t)
    {
        t--;

        int a, b, c, d, x, y;
        in>>a>>b>>c;
        d=gcd_ext(a, b, x, y);

        if(c%d!=0)
            out<<"0 0\n";
        else
            out<<x*(c/d)<<" "<<y*(c/d)<<'\n';
    }

    return 0;
}