Cod sursa(job #1500512)

Utilizator SzymonSidorSzymonSidor SzymonSidor Data 12 octombrie 2015 03:28:13
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <algorithm>
#include <stdio.h>
#include <iostream>
#include <fstream>

using namespace std;

int gcd(int a, int b) {
    if (b)
        return gcd(b, a % b);
    return a;
}

pair <int, int> coef(int a, int b) {
    if (!b)
        return make_pair(1, 0);
    pair <int, int> sol = coef(b, a % b);
    swap(sol.first, sol.second);
    sol.second -= (a / b) * sol.first;

    return sol;
}

int main() {
    ifstream cin("euclid3.in");
    freopen("euclid3.out", "w", stdout);

    int testCases, a, b, c;
    for (cin >> testCases; testCases; testCases--) {
        cin >> a >> b >> c;
        if (c % gcd(a, b) != 0)
            printf("0 0\n");
        else {
            pair <int, int> sol = coef(a, b);
            printf("%d %d\n", sol.first * c / gcd(a, b), sol.second * c / gcd(a, b));
        }
    }

    return 0;
}