Cod sursa(job #2666404)

Utilizator Chirac_MateiChiriac Matei Chirac_Matei Data 1 noiembrie 2020 18:46:41
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>

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

pair<long long, long long> euclid_extins(long long a, long long b)
{
    pair<long long, long long> pa={1, 0};
    pair<long long, long long> pb={0, 1};

    if(a<b)
    {
        swap(a, b);
        swap(pa, pb);
    }

    while(b>1)
    {
        long long nr=a/b;

        a-=nr*b;
        pa.first-=nr*pb.first;
        pa.second-=nr*pb.second;

        swap(a, b);
        swap(pa, pb);
    }

    return pb;
}
long long t,a,b,c,cmmdc,nr,ca,cb;
int main()
{
    fin>>t;
    while(t)
    {
        t--;
        fin>>a>>b>>c;

        if(a==0 && b==0)
        {
            fout<<"0 0\n";
            continue;
        }
        if(b==0)
        {
            if(c%a==0)
                fout<<c/a<<" 0\n";
            else
                fout<<"0 0\n";
            continue;
        }
        if(a==0)
        {
            if(c%b==0)
                fout<<"0 "<<c/b<<'\n';
            else
                fout<<"0 0\n";
            continue;
        }

        ca=a;
        cb=b;
        a=abs(a);
        b=abs(b);

        cmmdc=__gcd(a, b);
        if(c%cmmdc)
        {
            fout<<"0 0\n";
            continue;
        }

        nr=c/cmmdc;
        a/=cmmdc;
        b/=cmmdc;

        pair<long long, long long> ans=euclid_extins(a, b);
        ans.first*=nr;
        ans.second*=nr;

        if(ca<0)
            ans.first*=-1;
        if(cb<0)
            ans.second*=-1;

        fout<<ans.first<<' '<<ans.second<<'\n';
    }
    return 0;
}