Cod sursa(job #2666396)

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

using namespace std;
ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");
struct pos
{
    long long x, y;
    pos(){}
    pos(long long x, long long y)
    {
        this->x=x;
        this->y=y;
    }
    pos operator*(long long nr)
    {
        return pos(x*nr, y*nr);
    }
    pos operator-(pos b)
    {
        pos ans;
        ans.x=x-b.x;
        ans.y=y-b.y;
        return ans;
    }
};
pos euclid_extins(long long a, long long b)
{
    pos pa=pos(1, 0);
    pos pb=pos(0, 1);

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

    while(b>1)
    {
        long long nr=a/b;
        a-=nr*b;
        pa=pa-pb*nr;

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

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

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

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

        pos ans=euclid_extins(a, b);
        ans=ans*nr;

        fout<<ans.x<<' '<<ans.y<<'\n';
    }
    return 0;
}