Cod sursa(job #2924632)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 6 octombrie 2022 20:41:33
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;

using namespace std;

/*******************************/
// INPUT / OUTPUT

ifstream f("euclid3.in");
ofstream g("euclid3.out");
/*******************************/
/// GLOBAL DECLARATIONS

int T;
ll A, B, C;
ll x, y;
bool ok;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    f >> T;
}
///-------------------------------------
inline void Reset()
{
    x = 0, y = 0;
}
///-------------------------------------
ll gcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1;
    ll d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);

    return d;
}
///-------------------------------------
bool find_one_solution(ll a, ll b, ll c, ll &x0, ll &y0)
{
    ll g = gcd(abs(a), abs(b), x0, y0);

    if (c % g != 0)
        return false;
    
    x0 = x0 * (c / g);
    y0 = y0 * (c / g);

    if (a < 0) x0 = -x0;
    if (b < 0) y0 = -y0;

    return true;
}
///-------------------------------------
inline void Read()
{
    f >> A >> B >> C;
}
///-------------------------------------
inline void Solve()
{
    ok = find_one_solution(A, B, C, x, y);
}
///-------------------------------------
inline void Output()
{
    if (ok) g << x << " " << y << "\n";
    else
    {
        g << "0 0\n";
    }
}
///-------------------------------------
inline void TestCase()
{
    Reset();
    Read();
    Solve();
    Output();
}
///-------------------------------------
inline void Solution()
{
    while (T --)
    {
        TestCase();
    }
}
///-------------------------------------
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ReadInput();
    Solution();
    return 0;
}