Cod sursa(job #2471833)

Utilizator Leonard1998Olariu Leonard Leonard1998 Data 11 octombrie 2019 16:47:47
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

// Function for extended Euclidean Algorithm
int gcdExtended(int a, int b, int *x, int *y) {
    // Base Case
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }

    int x1, y1; // To store results of recursive call
    int gcd = gcdExtended(b%a, a, &x1, &y1);

    // Update x and y using results of recursive call
    *x = y1 - (b/a) * x1;
    *y = x1;

    return gcd;
}

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

    int t, x, y, a, b, c;
    scanf("%d", &t);

    while (t--) {
        scanf("%d %d %d", &a, &b, &c);

        int g = gcdExtended(a, b, &x, &y);
        if (c % g) printf("0 0\n");
        else printf("%d %d\n", x * (c / g), y * (c / g));
    }

    return 0;
}