Cod sursa(job #1898086)

Utilizator anderut22Sandu Andrei anderut22 Data 1 martie 2017 20:29:37
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
using namespace std;
ifstream cin("euclid3.in");
ofstream cout("euclid3.out");

int a, b, c, x, y, d, n;

int cmmdc(int a, int b);
void extEuc(int a, int b, int &x1, int &y1, int d);

int main()
{
    int i, dLocal, k;
    cin >> n;
    for (i=1; i<=n; i++)
    {
        cin >> a>> b>> c;
        dLocal=cmmdc(a, b);
        if (c%dLocal) cout << "0 0\n";
            else
            {
                k=c/dLocal;
                extEuc(a, b, x, y, dLocal);
                cout << x*k<< ' '<< y*k<< '\n';
            }
    }
    return 0;
}

int cmmdc(int a, int b)
{
    if (!b) return a;
    cmmdc(b, a%b);
}

void extEuc(int a, int b, int &x1, int &y1, int d)
{
    int rem;
    if (!b)
    {
        x1=1;
        y1=0;
        return;
    }
    extEuc(b, a%b, x1, y1, d);
    rem=x1;
    x=y1;
    y=rem-(a/b)*y1;
}