Cod sursa(job #1935479)

Utilizator andru47Stefanescu Andru andru47 Data 22 martie 2017 14:00:07
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;
inline void euclid_extins(int &x, int &y, int a, int b)
{
    if (b == 0)
        x = 1 , y = 0;
    else
    {
        euclid_extins(x , y, b , a % b);
        int aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}
inline int Gcd(int a , int b)
{
    int r = a % b;
    while(b)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
int main()
{
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);

    int Q;
    for (scanf("%d", &Q); Q; --Q)
    {
        int a , b ,c;
        scanf("%d %d %d", &a, &b, &c);
        int x , y;
        int gcd = Gcd(a , b);
        if (!(c % gcd))
        {
            euclid_extins(x , y, a, b);
            printf("%d %d\n", x * c / gcd, y * c / gcd);
        }
        else printf("0 0\n");
    }

    return 0;
}