Cod sursa(job #2865266)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 8 martie 2022 17:42:58
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>

using namespace std;

#pragma GCC optimize ("Ofast")

const string filename = "euclid3";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

long long n;

void big_euclid(long long a, long long b, long long &x, long long &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    big_euclid(b, a % b, x, y);
    long long aux = x;
    x = y;
    y = aux - (a / b) * y;

}

long long small_euclid(long long a, long long b)
{
    if(b == 0)
        return a;
    return small_euclid(b, a % b);
}

int main()
{
    fin >> n;
    for(long long i = 1; i <= n; i++)
    {
        long long a, b, c, x, y, cmmdc;
        fin >> a >> b >> c;
        cmmdc = small_euclid(a, b);
        if(c % cmmdc != 0)
        {
            fout << "0 0\n";
            continue;
        }
        big_euclid(a, b, x, y);
        x = x * c / cmmdc;
        y = y * c / cmmdc;
        fout << x << ' ' << y << '\n';
    }
    return 0;
}