Cod sursa(job #2800692)

Utilizator francescom_481francesco martinut francescom_481 Data 13 noiembrie 2021 18:25:50
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 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;
        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;
}