Cod sursa(job #342490)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 22 august 2009 00:19:14
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
int paramA[10000];
int paramB[10000];
int aux;
int a,b,c;
int x; int y;
int cmmdc;
int n;
int euclid(int a, int b)
{
    int aux;
    while (a%b)
     {
         paramA[++paramA[0]] = a;
         paramB[++paramB[0]] = b;
         aux = a;
         a = b;
         b = aux % b;

     }
     paramA[++paramA[0]] = a;
     paramB[++paramB[0]] = b;
    cmmdc = b;
}

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

    scanf("%d",&n);
    while (n)
    {
        x = 1; y = 0;
        scanf("%d %d %d",&a,&b,&c);
        euclid(a,b);
        for(int i = paramA[0]; i > 0; i--)
         {
             aux = x;
             x = y;
             y = aux - paramA[i] / paramB[i] * y;
         }
        if (c % cmmdc) printf("0 0\n");
                  else printf("%d %d\n",x*(c/cmmdc),y*(c/cmmdc));
        paramA[0] = paramB[0] = 0;
        n--;
    }
}