Cod sursa(job #199513)

Utilizator romocoderRomo Coder romocoder Data 19 iulie 2008 02:36:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
//@RomoCoder
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;
void go();
int main() {
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    
    int T;
    scanf("%d", &T);
    while (T--) go();
    return 0;
    }
pair<LL, LL> euclid(LL a, LL b)
{
         pair<LL, LL> R(1, 0);
         if (b == 0) return R;
         pair<LL, LL> X = euclid(b, a % b);
         R.first = X.second;
         R.second = X.first - (a / b) * X.second;          
         return R;
}
void go(){
     LL a, b, c;
     scanf("%lld%lld%lld", &a, &b, &c);
     LL G = __gcd(a, b);
     if (c % G != 0) {printf("0 0\n"); return;}
     G = c / G;
     pair<LL, LL> R = euclid(a, b);
     printf("%lld %lld\n", R.first * G, R.second * G);
     }

//RomoCoder in Action Again!