Cod sursa(job #2800695)

Utilizator francescom_481francesco martinut francescom_481 Data 13 noiembrie 2021 18:28:07
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
#define cin fin
#define cout fout

#define N 1005
int a, b, c, t, r;
struct cm
{
    int x,y;
};


int main()
{
    cin >> t;
    for( ; t ; t--)
    {
        cin >> a >> b >> c;
        if(a == 0)
        {
            if(c%b == 0)cout << 0 << " " << c/b << '\n';
            else cout << "0 0\n";
            continue;
        }
        if(b == 0)
        {
            if(c%a == 0)cout << c/a << " " << 0 << '\n';
            else cout <<"0 0\n";
            continue;
        }
        cm z, k;
        z.x = 1, z.y = 0;
        k.x = 0, k.y = 1;
        r = a%b;
        cm p;
        p.x = z.x-(a/b)*k.x;
        p.y = z.y-(a/b)*k.y;
        while(r != 0)
        {
            a = b;
            b = r;
            z = k;
            k = p;
            r = a%b;
            p.x = z.x-(a/b)*k.x;
            p.y = z.y-(a/b)*k.y;
        }
        if(c%b == 0)
        {
            cout << k.x*(c/b) << " " << k.y*(c/b)<< '\n';
        }
        else cout << "0 0\n";
    }
    return 0;
}