Cod sursa(job #657055)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 5 ianuarie 2012 18:23:58
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
using namespace std;

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

inline int cmmdc(int a, int b)
{
    ++pas;
    if (b == 0)
        return a;
    else
        return cmmdc(b, a % b);
}

int main()
{
    ifstream f("euclid3.in");
    ofstream g("euclid3.out");

    for (f >> t; t > 0; --t)
    {
        f >> a >> b >> c;
        pas = 0;
        int d = cmmdc(a, b);
        x = 1;
        y = 0;

        if (c % d) g << "0 0\n";
        else
        {
            for (int i = 1; i <= pas; ++i)
            {
                int dx = x, dy = y;
                x = dy;
                y = dx - (a / b) * dy;
            }
            g << x * (c / d) << ' ' << y * (c / d) << '\n';
        }
    }

    g.close();
    return 0;
}