Cod sursa(job #1375199)

Utilizator darrenRares Buhai darren Data 5 martie 2015 12:33:47
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstring>
#include <fstream>
#include <algorithm>

using namespace std;

int T;

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}
pair<int, int> gcex(int a, int b, int c)
{
    if (b == 0)
        return make_pair(c, 0);

    pair<int, int> old = gcex(b, a % b, c);
    return make_pair(old.second, old.first - (a / b) * old.second);
}

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

    fin >> T;
    while (T--)
    {
        int A, B, C;
        fin >> A >> B >> C;

        int D = gcd(A, B);
        if (C % D != 0)
            fout << 0 << ' ' << 0 << '\n';
        else
        {
            A /= D;
            B /= D;
            C /= D;

            pair<int, int> res = gcex(A, B, C);
            fout << res.first << ' ' << res.second << '\n';
        }
    }

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