Cod sursa(job #2870084)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 12 martie 2022 08:04:47
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb

#include <iostream>
#include <fstream>

using namespace std;

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

int n;

void euclid_extins(int a, int b, long long &x, long long &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    euclid_extins(b, a % b, x, y);
    int ax, ay;
    ax = y;
    ay = x - 1LL * (a / b) * y;
    x = ax, y = ay;
}

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

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        bool invers = 0;
        int a, b, c, d;
        long long x, y;
        fin >> a >> b >> d;
        if(a < b)
            swap(a, b), invers = 1;
        c = euclid(a, b);
        if(d % c != 0)
        {
            fout << "0 0\n";
            continue;
        }
        euclid_extins(a, b, x, y);
        x = x * d / c;
        y = y * d / c;
        if(invers)
            swap(x, y);
        fout << x << ' ' << y << '\n';
    }
    return 0;
}