Cod sursa(job #2054669)

Utilizator Andrei2000Andrei Mihailescu Andrei2000 Data 2 noiembrie 2017 12:15:06
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

ll euclid(ll q, ll qq,ll &x0 ,ll &y0){
    ll E,x=0,y=1,c,r;
    x0=1,y0=0;
    while(qq){
        c=q/qq;
        r=q%qq;
        q=qq;
        qq=r;
        r=x0;
        x0=x;
        x=r-c*x;
        r=y0;
        y0=y;
        y=r-c*y;
    }
    return q;
}

int main()
{
    ll a,b,E,x,y,c,T;
    fin>>T;
    while(T--){
        fin>>a>>b>>c;
        E=euclid(a,b,x,y);
        if(c%E)fout<<0<<' '<<0<<'\n';
        else fout<<x*c/E<<' '<<y*c/E<<'\n';
    }
    return 0;
}