Cod sursa(job #764184)

Utilizator mi5humihai draghici mi5hu Data 4 iulie 2012 12:45:33
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>

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

int main()
{
    int t;
    freopen ("euclid3.in", "r", stdin);
    freopen ("euclid3.out", "w", stdout);
    int i, a, b, c, d, x, y;

    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        scanf("%d%d%d", &a, &b, &c);
    
        euclid(a, b, &d, &x, &y);
        if (c%d == 0) {
           printf("%d %d\n", x * c / d, y * c / d);
        }
        else {
           printf("0 0\n");
        }
    }
    return 0;
}