Cod sursa(job #3330610)

Utilizator Anul2024Anul2024 Anul2024 Data 20 decembrie 2025 14:12:14
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
using namespace std;
ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");
void calc (int a, int b, int &x, int &y, int &d)
{
    if (b == 0)
    {
        d = a;
        x = 1;
        y = 0;
    }
    else
    {
        int xn, yn;
        calc (b, a % b, xn, yn, d);
        ///a * x + b * y = d
        ///b * x + r * y = d
        ///a = qb + r
        ///b * x + (a - qb) * y = d
        ///a * y + b * (x - qy) = d
        x = yn;
        y = xn - (a / b) * yn;
    }
}
int main ()
{
    ///c tb sa fie multiplu de d, altfel ce e in stanga e multiplu de d => nu avem solutie
    int t, a, b, c, d, x, y;
    fin >> t;
    while (t--)
    {
        fin >> a >> b >> c;
        calc (a, b, x, y, d);
        if (c % d == 0)
            fout << x * (c / d) << " " << y * (c / d) << "\n";
        else
            fout << "0 0\n";
    }
    return 0;
}