Cod sursa(job #2559027)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 26 februarie 2020 22:16:52
Problema Algoritmul lui Euclid extins Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int a,b,c;

typedef long long ll;

int cmmdc(int a, int b)
{
    int r;
    while(b)
    {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}


void euclid(ll a, ll b, ll& d, ll& x, ll& y)
{
    if (b == 0) {
        d = a;
        x = 1;
        y = 0;
    } else {
        ll x0, y0;
        euclid(b, a % b, d, x0, y0);
        x = y0;
        y = x0 - (a / b) * y0;
    }
}

void Do()
{
    ll i,j,x,y,d,g;
    fin>>a>>b>>c;
    g = cmmdc(a,b);
    if(c%g != 0)
    {
        fout<<0<<" "<<0;
        return ;
    }
    else
    {
        d = g;
        euclid(a,b,d,x,y);
        d = c/g;
        fout<<x*d<<" "<<y*d<<"\n";
    }
}

int main()
{
    int test,i;
    fin>>test;
    for(i=1; i<=test; ++i)
        Do();
    return 0;
}