Cod sursa(job #2848115)

Utilizator raresmihociMihoci Rares raresmihoci Data 12 februarie 2022 10:13:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
long long t, a, b, c, x, y, d;

void euclid(long long a , long long b ,long long &d, long long &x ,long long &y);
long long cmmdc(long long a, long long b);

int main()
{

    fin >> t;
    for(int i = 1; i <= t; i++)
    {
        fin >> a >> b >> c;
        d = cmmdc(a, b);
        long long x = 0, y = 0;
        if(c % d == 0)
        {
            euclid(a, b ,d ,x ,y);
            fout << x * c / d << ' ' << y * c / d << endl;
        }
        else
            fout << "0 0" << endl;

    }
    return 0;
}

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

void euclid(long long a , long long b ,long long &d, long long &x ,long long &y)
{
    if(b == 0)
    {
        d = a;
        x = 1; y = 0;
    }
    else
    {
        long long x1 = 0 , y1 = 0;
        euclid(b , a % b , d, x1 , y1);
        x = y1;
        y = x1 - (a / b) * y1;
    }
}