Cod sursa(job #3221817)

Utilizator proflaurianPanaete Adrian proflaurian Data 8 aprilie 2024 10:11:18
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
int64_t cmmdc(int64_t a,int64_t b,int64_t &x,int64_t &y)
{
    /// oare ce fac daca b=0?
    /// d=a a*1+b*0=d x=1,y=0
    if(b==0)
    {
        x=1;y=0;
        return a;
    }

    /// daca b!=0
    int64_t X,Y,D;
    D=cmmdc(b,a%b,X,Y);
    x=Y;
    y=X-(a/b)*Y;
    return D;
}
void solve(int64_t a,int64_t b,int64_t c)
{
    int64_t x,y,d;
    d=cmmdc(a,b,x,y);
    if(c%d!=0)
    {
        g<<"0 0\n";
        return;
    }
    x*=c/d;
    y*=c/d;
    g<<x<<' '<<y<<'\n';
}
int main()
{
    int64_t t,a,b,c;
    f>>t;
    for(;t;t--)
    {
        f>>a>>b>>c;
        solve(a,b,c);
    }
    return 0;
}