Cod sursa(job #1494850)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 1 octombrie 2015 22:04:17
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
///Solutie explicata de marele matematician Tudor Bonifate

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll T , a , b , c , cmmdc;
ll X0 , X1 , Y0 , Y1 , x , y , r;

ll gcd(ll a , ll b)
{
    if (!b) return 0;

    ll r = a % b;

    while (r)
    {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

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

    for (scanf("%lld", &T); T; --T)
    {
        scanf("%lld %lld %lld", &a, &b, &c);

        if (!a && !b) {printf("0 0\n"); continue;}

        cmmdc = gcd(a , b);

        if (!a && b == c) {printf("0 1\n"); continue;}
        if (a == c && !b) {printf("1 0\n"); continue;}

        if (!cmmdc || c % cmmdc)
        {
            printf("0 0\n");
            continue;
        }

        X0 = 1; X1 = 0; Y0 = 0; Y1 = 1;
        r = a % b;
        while (r)
        {
            x = X0 - (a / b) * X1; X0 = X1; X1 = x;
            y = Y0 - (a / b) * Y1; Y0 = Y1; Y1 = y;
            a = b; b = r; r = a % b;
        }

        printf("%lld %lld\n", x * c / cmmdc , y * c / cmmdc);
    }

    return 0;
}