Cod sursa(job #1497770)

Utilizator stefanzzzStefan Popa stefanzzz Data 7 octombrie 2015 12:00:39
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
#include <stdlib.h>
#define INF 2000000000
using namespace std;

int nrt, a, b, c;

int euclid(int a, int b, long long &x, long long &y) {
    if(!b) return a;
    int ans = euclid(b, a % b, x, y);
    long long xnew = y, ynew = x - a / b * y;
    x = xnew, y = ynew;
    return ans;
}

int main()
{
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);

    scanf("%d", &nrt);
    while(nrt--) {
        scanf("%d %d %d", &a, &b, &c);
        long long x = 1, y = 0;
        int d = euclid(abs(a), abs(b), x, y);
        if(c % d != 0) printf("0 0\n");
        else {
            x *= c / d;
            y *= c / d;

            if(a < 0) x = -x;
            if(b < 0) y = -y;
            printf("%lld %lld\n", x, y);
        }
    }

    return 0;
}