Cod sursa(job #2640894)

Utilizator loraclorac lorac lorac Data 8 august 2020 22:05:52
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");
typedef long long ll;
ll tst,a,b,c;
ll d,coef_a,coef_b;
void gcd(ll a,ll b)
{
    ll pa=a,pb=b;
    a=abs(a);
    b=abs(b);
    ll r,cnt,ca=1,cb=0,cca=0,ccb=1;
    ll auxa,auxb;
    if(a>b and b!=0)
        auxa=1,auxb=-(a/b-1);
    else if(a>b)
        auxa=1,auxb=0;
    else if(a<=b and a!=0)
        auxa=-(b/a-1),auxb=1;
    else auxa=0,auxb=1;
    ll befa=auxa,befb=auxb;
    while(b)
    {
        r=a%b;
        cnt=a/b;
        befa=auxa;
        befb=auxb;
        auxa=(ca-cca*cnt);
        auxb=(cb-ccb*cnt);
        a=b;
        ca=cca;
        cb=ccb;
        b=r;
        cca=auxa;
        ccb=auxb;
    }
    coef_a=befa;
    coef_b=befb;
    d=a;
    if(pa<0) coef_a=-coef_a;
    if(pb<0) coef_b=-coef_b;
}
int main()
{
    in>>tst;
    while(tst--)
    {
        in>>a>>b>>c;
        gcd(a,b);
        if(d==0 or abs(c)%d!=0) {out<<"0 0\n";continue;}
        out<<coef_a*(c/d)<<' '<<coef_b*(c/d)<<'\n';
    }
    return 0;
}