Cod sursa(job #148503)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 4 martie 2008 13:55:34
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <stdio.h>

long a,b,c,d,x,y,t;

long euclid_e(long A,long B,long &X,long &Y){
    if (B==0){
        X=1;
        Y=0;
        return A;
    }
    long x0,y0,D;
    D=euclid_e(B,A%B,x0,y0);
    X=y0;
    Y=x0-(A/B)*y0;
    return D;
}

int main(){
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    
    scanf("%ld",&t);
    for (;t;t--){
        scanf("%ld %ld %ld",&a,&b,&c);

        d=euclid_e(a,b,x,y);
        
        if (c%d!=0)printf("0 0\n");
        else printf("%ld %ld\n",x*(c/d),y*(c/d));
    }

return 0;   
}