Cod sursa(job #2232537)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 19 august 2018 21:19:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>

using namespace std;

ifstream cin("euclid3.in");
ofstream cout("euclid3.out");

int gcd(int a, int b, int & c1, int & c2) {
    if (b == 0) {
        c1 = 1;
        c2 = 0;
        return a;}
    int auxc1, auxc2;
    int ans = gcd(b, a % b, auxc1, auxc2);
    c1 = auxc2;
    c2 = 1LL * auxc1 - (a / b) * auxc2;
    return ans;
}

int main()
{
    int t, a, b, ans;
    cin >> t;
    while (t--) {
        cin >> a >> b >> ans;
        int x, y;
        int p = gcd(a, b, x, y);
        if (ans % p)
            cout << "0 0\n";
        else
            cout << 1LL * x * ans / p << ' ' << 1LL * y * ans / p << '\n';
    }
    return 0;
}