Cod sursa(job #2593174)

Utilizator bcosminbcosmin bcosmin Data 3 aprilie 2020 08:30:40
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>
using namespace std;

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

long long i, n, X1, X2, Y1, Y2, x, y, rest1, rest2, rest, d, val, cat;

int main()
{
    f >> n;
    for(i = 1; i <= n; ++ i)
    {
        f >> rest1 >> rest2 >> d;
        if(rest1 == 0 || rest2 == 0)
        {
            if(rest1 == 0)
            {
                if(d % rest2 == 0)
                    g << "0 " << d / rest2 << "\n";
                else
                    g << "0 0" << "\n";
            }
            else
            {
                if(d % rest1 == 0)
                    g << d / rest1 << " 0" << "\n";
                else
                    g << "0 0" << "\n";
            }
        }
        else
        {
            val = __gcd(rest1, rest2);
            X1 = 1;
            X2 = 0;
            Y1 = 0;
            Y2 = 1;
            if(d % val != 0)
                g << "0 0" << "\n";
            else
            {
                while(rest1 % rest2 != 0)
                {
                    cat = rest1 / rest2;
                    rest = rest1 % rest2;
                    rest1 = rest2;
                    rest2 = rest;
                    x = X1 - cat * X2;
                    y = Y1 - cat * Y2;
                    X1 = X2;
                    X2 = x;
                    Y1 = Y2;
                    Y2 = y;
                }
                g << X2 * (d / val) << " " << Y2 * (d / val) << "\n";
            }
        }
    }
    return 0;
}