Cod sursa(job #1494842)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 1 octombrie 2015 21:55:48
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 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)
{
    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);

        cmmdc = gcd(a , b);

        if (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;
}