Cod sursa(job #2784283)

Utilizator George_CristianGeorge Dan-Cristian George_Cristian Data 16 octombrie 2021 11:25:45
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <iostream>

using namespace std;

pair<long long, long long> euclid_extins(long long x, long long y) {
    if (y == 0)
        return {1, 0};
    auto p = euclid_extins(y, x % y);
    return {p.second, p.first - (x / y) * p.second};
}

int main() {
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    long long n, a, b, c;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld%lld%lld", &a, &b, &c);
        auto p = euclid_extins(a, b);
        long long d = a * p.first + b * p.second;
        if (c % d)
            printf("0 0\n");
        else
            printf("%lld %lld\n", p.first * c / d, p.second * c / d);
    }
    return 0;
}