Cod sursa(job #1723602)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 1 iulie 2016 00:13:16
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>

using namespace std;

void extended_euclid(long long A,long long B, long long *C, long long *X, long long *Y){
    if(B == 0)
    {
        *X = 1;
        *Y = 0;
        *C = A;
        return;
    }
    long long newX,newY;
    extended_euclid(B,A%B,C,&newX,&newY); /// newX* B + newY * (A - [A/B]*B) = A * X + B * Y
    *X = newY;
    *Y = newX - A/B*newY;
}

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

    int N;
    scanf("%d",&N);
    long long A,B,C,D;

    for(int i = 1; i <= N; ++i)
    {
        scanf("%lld%lld%lld",&A,&B,&D);
        long long X,Y;
        extended_euclid(A,B,&C,&X,&Y);
        if(D % C != 0)
            printf("0 0\n");
        else
            printf("%lld %lld\n",X * D/C, Y * D/C);
    }

    return 0;
}