Cod sursa(job #3213187)

Utilizator AlexInfoIordachioaiei Alex AlexInfo Data 12 martie 2024 17:34:29
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("euclid3.in");
ofstream out("euclid3.out");

#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

const int NMAX = 1e5 + 30;
const int INF = 0x3f3f3f3f;

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

void read()
{
    in >> t;
}

void euclid(int a, int b, int &d, int &x, int &y)
{
    if (b == 0)
    {
        d = a; // ultimul rest e 0, returnam penultimul rest si a * 1 + 0 * y = a
        x = 1, y = 0;
        return;
    }
    int x1, y1;
    // a = b * c + r, unde c = a / b, deci r = a - b * c
    euclid(b, a % b, d, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
}

void solve()
{
    while (t--)
    {
        in >> a >> b >> c, euclid(a, b, d, x, y);
        if (c % d == 0) // transformam ecuatia a*x+b*y = d in a*u + b*v = c, prin inmultire cu c/d daca se imparte exact
            out << x * (c / d) << ' ' << y * (c / d) << '\n';
        else
            out << 0 << ' ' << 0 << '\n';
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    read();
    solve();

    return 0;
}