Cod sursa(job #2784276)

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

using namespace std;

typedef long long ll;

short TESTS;
ll a, b, c;

pair<ll, ll> euclidExtins(ll X, ll Y) {
    if(!Y) return {1, 0};
    pair<ll, ll> 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("%lld%lld%lld", &a, &b, &c);
        pair<ll, ll> p = euclidExtins(a, b);
        ll cmmdc = 1ll * a * p.first + b * p.second;
        if(c % cmmdc) printf("0 0\n");
        else printf("%lld %lld\n", p.first * c / cmmdc, p.second * c / cmmdc);
    }
    return 0;
}