Cod sursa(job #1193099)

Utilizator ZenusTudor Costin Razvan Zenus Data 30 mai 2014 23:03:19
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <cstdio>

using namespace std;

int T,A,B,C,D,Inv,Ins;

int Gcd(int A,int B,int &Inv,int &Ins)
{
    int HInv=0,HIns=0;

    if (!B)
    {
        Inv=1;
        Ins=0;
        return A;
    }

    D=Gcd(B,A%B,HInv,HIns);

    Inv=HIns;
    Ins=HInv-(A/B)*HIns;

    return D;

}

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

scanf("%d",&T);

while (T--)
{
    scanf("%d%d%d",&A,&B,&C);

    D=Gcd(A,B,Inv,Ins);

    if (C%D)
    {
        printf("0 0\n");
        continue;
    }

    printf("%d %d\n",Inv*(C/D),Ins*(C/D));
}

return 0;
}