Cod sursa(job #3004534)

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

#define int long long

using namespace std;

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

pair<int, int> get(int a, int b)
{
    if (b == 0)
    {
        return {1, 0};
    }
    pair<int, int> x = get(b, a % b);
    pair<int, int> ans;
    ans.first = x.second;
    ans.second = x.first - x.second * (a / b);
    return ans;
}

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 = gcd(a, b);
        pair<int, int> ans = get(a, b);
        if (c % val == 0)
        {
            fout << ans.first * c / val << ' ' << ans.second * c / val << '\n';
        }
        else
        {
            fout << 0 << ' ' << 0 << endl;
        }
    }
}