Cod sursa(job #2865262)

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

using namespace std;

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

int n;

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

}

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

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        int 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;
}