Cod sursa(job #3004544)

Utilizator tibinyteCozma Tiberiu-Stefan tibinyte Data 16 martie 2023 13:23:20
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

#define int long long

using namespace std;

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

tuple<int, int, int> get(int a, int b)
{
    if (b == 0)
    {
        return {a, 1, 0};
    }
    tuple<int, int, int> x = get(b, a % b);
    return {get<0>(x), get<2>(x), get<1>(x) - get<2>(x) * (a / b)};
}

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    fin >> q;
    while (q--)
    {
        int a, b, c;
        fin >> a >> b >> c;
        int val, x, y;
        tie(val, x, y) = get(a, b);
        if (c % val == 0)
        {
            fout << x * c / val << ' ' << y * c / val << '\n';
        }
        else
        {
            fout << 0 << ' ' << 0 << '\n';
        }
    }
}