Cod sursa(job #2571018)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 4 martie 2020 20:29:44
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("euclid2.in");
ofstream out("euclid2.out");
int t,a,b,c,x,y,d;
int cmmdc(int a,int b)
{
    if(b==0) return a;
    else return cmmdc(b,a%b);
}
void gcd(int a,int b,int &x,int &y)
{
    if(b==0) {
     x=1;
     y=0;
    }
    else
    {
        int x0,y0;
        gcd(b,a%b,x0,y0);
        x=y0;
        y=x0-(a/b)*y0;
    }
}
int main()
{
    in>>t;
    while(t--)
    {
        in>>a>>b>>c;
        d=cmmdc(a,b);
        if(c%d!=0)
        {
            out<<0<<" "<<0<<'\n';
            continue;
        }
        gcd(a,b,x,y);
        out<<1LL*x*c/d<<" "<<1LL*y*c/d<<'\n';
    }
    return 0;
}