Cod sursa(job #2499051)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 25 noiembrie 2019 10:41:46
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
int gcdExtended (int a, int b, int &x, int &y) {
        if (a == 0) {
                x = 0;
                y = 1;
                return b;
        }

        int x1, y1;
        int gcd = gcdExtended (b % a, a, x1, y1);
        x = y1 - (b / a) * x1;
        y = x1;
        return gcd;
}
int main() {
        freopen ("euclid3.in", "r", stdin);
        freopen ("euclid3.out", "w", stdout);
        int x, y, a, b, c, n;
        scanf ("%d", &n);
        for (int i = 1; i <= n; ++i) {
                scanf ("%d %d %d", &a, &b, &c);
                int num = gcdExtended (a, b, x, y);
                if (c % num) {
                        printf ("0 0\n");
                } else {
                        printf ("%d %d\n", x * (c / num), y * (c / num));
                }
        }
        return 0;
}