Cod sursa(job #2354244)

Utilizator mihai.alphamihai craciun mihai.alpha Data 25 februarie 2019 07:30:07
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

long long t;

void gcd(long long a, long long b, long long &x, long long &y)  {
    if(b == 0LL)  {
        x = 1LL;
        y = 0LL;
        return;
    }
    long long x1, y1;
    gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
}

int main()  {
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    scanf("%lld", &t);
    while(t--)  {
        long long a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        if(c % __gcd(a, b) != 0LL)  {
            printf("0 0\n");
        }
        else  {
            long long x, y;
            //long long aa = gcd(a, b, x, y);
            long long aa = __gcd(a, b);
            gcd(a, b, x, y);
            c = c / aa;
            x *= c, y *= c;
            if(x * a + y * b == -c)
                x *= -1LL, y *= -1LL;
            printf("%d %d\n", x, y);
        }
    }
    return 0;
}