Cod sursa(job #2784274)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 16 octombrie 2021 11:16:26
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>

using namespace std;

short TESTS;
int a, b, c;

pair<int, int> euclidExtins(int X, int Y) {
    if(!Y) return {1, 0};
    pair<int, int> p = euclidExtins(Y, X % Y);
    return {p.second, p.first - p.second * (X / Y)};
}

int main()
{
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    scanf("%hd", &TESTS);
    while(TESTS--) {
        scanf("%d%d%d", &a, &b, &c);
        pair<int, int> p = euclidExtins(a, b);
        int cmmdc = a * p.first + b * p.second;
        if(c % cmmdc) cout << "0 0\n";
        else cout << p.first * c / cmmdc << " " << p.second * c / cmmdc << "\n";
    }
    return 0;
}