Cod sursa(job #2974773)

Utilizator 100pCiornei Stefan 100p Data 4 februarie 2023 16:46:17
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

#define MAX 1024
#define int long long

#define FILES freopen("euclid3.in","r",stdin);\
              freopen("euclid3.out","w",stdout);

using namespace std;

int t;

int gcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    else
    {
        int cmm = gcd(b, a % b, x, y);

        int newX = y, newY = x - (a / b) * y;
        x = newX, y = newY;
        return cmm;
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    FILES
    cin >> t;
    for(int i = 1; i <= t; ++i)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        int sol1 = 0, sol2 = 0;
        int cmdc = gcd(a, b, sol1, sol2);
        if(c % cmdc)
        {
            std::cout << "0 0\n";
            continue;
        }

        std::cout << sol1 * (c / cmdc) << ' ' << sol2 * (c / cmdc) << '\n';
    }
}