Cod sursa(job #1412058)

Utilizator irimiecIrimie Catalin irimiec Data 1 aprilie 2015 08:47:37
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

#define     mp              make_pair
#define     fs              first
#define     sc              second
#define     pob             pop_back
#define     pub             push_back
#define     eps             1E-7
#define     sz(a)           a.size()
#define     count_one       __builtin_popcount;
#define     count_onell     __builtin_popcountll;
#define     fastIO          ios_base::sync_with_stdio(false)
#define     PI              (acos(-1.0))
#define     linf            (1LL<<62)//>4e18
#define     inf             (0x7f7f7f7f)//>2e9

#define MAXN 100

int cmmdc(int x, int y) {
    if(!y) return x;
    return cmmdc(y, x % y);
}

int euclid(int a, int b, int &x, int &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    } else {
        int x0, y0, d;
        d = euclid(b, a%b, x0, y0);
        x = y0;
        y = x0 - (a/b) * y0;
        return d;
    }
}

void read() {
    #ifndef ONLINE_JUDGE
    assert(freopen("euclid3.in", "r", stdin));
    assert(freopen("euclid3.out", "w", stdout));
    #endif

    int T;
	scanf("%d", &T);
	int a, b, c;
	while(T--) {
        scanf("%d%d%d", &a, &b, &c);
	    int d = cmmdc(a, b);
	    if(c % d)
	        printf("0 0\n");
        else {
            int x0, y0;
            euclid(a, b, x0, y0);
            printf("%d %d\n", x0 * (c/d), y0 * (c/d));
        }
	}
}

int main() {
	read();

    return 0;
}