Cod sursa(job #641141)

Utilizator guppyTanasoiu Bogdan guppy Data 27 noiembrie 2011 13:43:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#define N 10000

using namespace std;
int sol;
int C[N];

void computeSol(int a, int b, int c) {
    C[0] = 0;
    while(b != 0) {
        C[++C[0]] = a / b;
        int aux = a;
        a = b;
        b = aux % b;
    }
    int x = 1;
    int y = 0;
    for(int j = C[0]; j > 0; j--) {
        int auxx = x;
        x = y;
        y = auxx - C[j] * y;
    }
    if(c % a == 0)
     printf("%d %d\n",(c/a) * x, (c / a) * y);
    else
     printf("%d %d\n",0, 0);
}
int main()
{
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);

    int tc;
    scanf("%d",&tc);

    while(tc) {
        int a, b, d;
        tc--;
        scanf("%d %d %d",&a,&b,&d);
        computeSol(a,b,d);
    }
    return 0;
}