Cod sursa(job #2302962)

Utilizator Salamandra01Felmeri Zsolt Salamandra01 Data 15 decembrie 2018 12:02:37
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;

int extEuclid(int a, int b, int *x, int *y)
{
    if(!b){
        *x = 1;
        *y = 0;
        return a;
    }
    else{
        int x0, y0, d;
        d = extEuclid(b, a%b, &x0, &y0);

        *x = y0;
        *y = x0 - (a/b) * y0;
        return d;
    }
}

int main()
{
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    int T, a, b, c;
    int x, y, d;

    scanf("%i", &T);

    while(T--){
        scanf("%i%i%i", &a, &b, &c);
        d = extEuclid(a, b, &x, &y);

        if(c % d){
            printf("0 0\n");
        }
        else{
            printf("%i %i\n", x * (c / d), y * (c / d));
        }
    }

    return 0;
}