Cod sursa(job #3317841)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 25 octombrie 2025 16:37:01
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include<iostream>
#include<fstream>
#include <numeric>

using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

long long int n, a, b, c, minDiv, d, x, y;

long long int gcd(int a1, int b1)
{
    while (b1)
    {
        int r = a1 % b1;
        a1 = b1;
        b1 = r;
    }
    return a1;
}

void euclid(long long int a, long long int b, long long int &d, long long int &x, long long int &y)
{
    if (b == 0)
    {
        d = a;
        x = 1, y = 0;
    }
    else
    {
        long long int x1, y1;
        euclid(b, a % b, d, x1, y1);
        x = y1;
        y = x1 - a / b * y1;
    }
}

int main()
{
    bool aSign = 1, bSign = 1, cSign = 1;
    fin >> n;
    for (int i = 0; i < n; i++)
    {
        fin >> a >> b >> c;
        if (a < 0)
            aSign = 0;
        if (b < 0)
            bSign = 0;
        if (c < 0)
            cSign = 0;
        minDiv = gcd(a, b);
        if (c % minDiv > 0)
        {
            fout << "0 0\n";
            cout << "0 0\n";
            continue;
        }
        euclid(a, b, d, x, y);

        x *= c / minDiv;
        y *= c / minDiv;

        if (cSign == 0)
        {
            x *= -1;
            y *= -1;
        }
        if (aSign == 0)
            x *= -1;
        if (bSign == 0)
            y *= -1;
        fout << x << " " << y << "\n";
        cout << x << " " << y << "\n";
    }
}