Cod sursa(job #1188298)

Utilizator xtreme77Patrick Sava xtreme77 Data 19 mai 2014 11:53:55
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>

using namespace std;
int euclid(int a,int b,int &x,int &y);
int main()
{
    int a,b,c,t;
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        int rez1,rez2,sol;
        scanf("%d%d%d",&a,&b,&c);
        rez1=rez2=1<<17;
        sol=euclid(a,b,rez1,rez2);
        if(c%sol){
            printf("0 0 \n");
        }
        else printf("%d %d\n",rez1*(c/sol),rez2*(c/sol));
    }
    return 0;
}
int euclid(int a,int b,int &x,int &y)
{
    if (b==0){
       x=1;y=0;
       return a;
    }
    else{
        int x1,y1;
        int d;
        d=euclid(b,a%b,x1,y1);
        x=y1;
        y=x1-(a/b)*y1;
        return d;
    }
}