Cod sursa(job #2013077)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 20 august 2017 14:13:10
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

void euclid(long long A, long long B, long long *D, long long *X, long long *Y)
{
    if (!B) {
        *X = 1;
        *Y = 0;
        *D = A;
        return;
    }
    long long X0, Y0;
    euclid(B, A%B, D, &X0, &Y0); /// B * X0 + (A - [A/B]*B) * Y0
    *X = Y0;
    *Y = X0 - (A/B)*Y0;
}


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

    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        long long A, B, C;
        scanf("%lld%lld%lld", &A, &B, &C);
        long long D, X, Y;

        euclid(A, B, &D, &X, &Y);
        if(C % D != 0)
            printf("0 0\n");
        else
            printf("%lld %lld\n", C/D * X, C/D * Y);
    }

    return 0;
}