Cod sursa(job #1182116)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 4 mai 2014 21:09:21
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>
using namespace std;
int a, b, c, t, cat[1000], nc;
int main()
{
    int x0, y0, x, y, r;
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    scanf("%d", &t);
    while(t--){
        scanf("%d%d%d", &a, &b, &c);
        nc = 0;
        while((r=a%b)){
            cat[++nc] = a/b;
            a = b;
            b = r;
        }
        cat[++nc] = a/b;
        x0 = 1; y0 = 0;
        while(nc){
            x = y0;
            y = x0-cat[nc--]*y0;
            x0 = x; y0 = y;
        }
        if(c%b==0)
            printf("%d %d\n", x*(c/b), y*(c/b));
        else printf("0 0\n");
    }
    return 0;
}