Cod sursa(job #2437884)

Utilizator ALEx6430Alecs Andru ALEx6430 Data 10 iulie 2019 16:57:28
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

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

int main()
{
    int t;
    in >> t;

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

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

        int gcd = __gcd(a,b);

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

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

        if(a == ab.second) swap(V[0],V[1]);

        int n = 2;

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

        int r = q1 % q2;

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

            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++;
        }

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

        int alfa = c/gcd;

        x *= alfa; y *= alfa;

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

    return 0;
}