Cod sursa(job #3232328)

Utilizator mirzoca_raduMirzoca Radu Casian mirzoca_radu Data 29 mai 2024 22:01:42
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>

using namespace std;

int gcd(int a, int b)
{
    int r;
    while (b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

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

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

int main()
{
    int n;
    fin >> n;

    for (; n; n--)
    {
        int a, b, d;
        fin >> a >> b >> d;
        int gcd_ab = gcd(a, b);
        if (d % gcd_ab == 0)
        {
            int x = 1, y = 0;
            euclid_extins(x, y, a, b);
            fout << x << ' ' << y << endl;
        }
        else
        {
            fout << "0 0" << endl;
        }
    }

    fin.close();
    fout.close();
    return 0;
}