Cod sursa(job #1611512)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 24 februarie 2016 10:39:40
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<cstdio>

using namespace std;

int t,a,b,c;
int d;
int keepx,keepy,oldx,oldy;

int cmmdc(int x,int y)
{
    if(y==0)
    {
        return x;
    }
    return cmmdc(y,x%y);
}

void solve(int v1,int v2)
{
    if(v2==0)
    {
        oldx=1;
        oldy=0;
        return;
    }
    solve(v2,v1%v2);
    keepx=oldy;
    keepy=oldx-(v1/v2)*oldy;
    oldx=keepx;
    oldy=keepy;
}

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

    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        d=cmmdc(a,b);
        if(c%d!=0)
        {
            printf("0 0\n");
        }
        else
        {
            solve(a,b);
            keepx*=(c/d);
            keepy*=(c/d);
            printf("%d %d\n",keepx,keepy);
        }
    }
}