Cod sursa(job #2437899)

Utilizator ALEx6430Alecs Andru ALEx6430 Data 10 iulie 2019 17:34:18
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

int sign(int x)
{
    return x < 0 ? -1 : 1;
}

int main()
{
    int t;

    in >> t;

    while(t--)
    {
        int a, b, c;
        in >> a >> b >> c;

        pair<int,int> ab = {max(abs(a),abs(b)), min(abs(a),abs(b))};

        int gcd = __gcd(abs(a),abs(b));

        if(c % gcd != 0)
        {
            out << "0 0" << '\n';
            continue;
        }

        vector<pair<int,int>> V = {
                                    {1,0},
                                    {0,1}
                                            };

        if(a == 0)
        {
            out << 0 << ' ' << c/b << '\n';
            continue;
        }

        if(b == 0)
        {
            out << c/a << ' ' << 0 << '\n';
            continue;
        }

        int n = 2;

        int q1 = ab.first;
        int q2 = ab.second;

        int r = q1 % q2;

        while(r)
        {
            int q = q1/q2;
            r = q1%q2;

            q1 = q2*q + r;

            q1 = q2;
            q2 = r;

            int x = V[n-2].first - q*V[n-1].first;
            int y = V[n-2].second - q*V[n-1].second;

            pair<int,int> p = {x,y};

            V.push_back(p); n++;

            if(r == gcd) break;
        }

        int x = V[n-1].first;
        int y = V[n-1].second;

        int alfa = c/gcd;

        if(abs(a) == ab.second) swap(x,y);

        x *= alfa; y *= alfa;
        x *= sign(a); y *= sign(b);

        out << x << ' ' << y << '\n';
    }

    return 0;
}