Cod sursa(job #3185807)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 20 decembrie 2023 15:08:14
Problema Algoritmul lui Euclid extins Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

#define int long long

using namespace std;

int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else 
    {
        return gcd(b, a % b);
    }
}

void euclid(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
    }
    else
    {
        int x0, y0;
        euclid(b, a % b, x0, y0);
        x = y0;
        y = x0 - a / b * y0;
    }
}

signed main()
{
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");
    int t;
    fin >> t;
    while (t--)
    {
        int a, b, c;
        fin >> a >> b >> c;
        /// a * z + b * t = c 
        /// fie d = cmmdc(a, b)
        int d = gcd(a, b);
        /// daca c % d != 0 nu avem solutii
        if (c % d)
        {
            fout << "0 0\n";
            return 0;
        }
        /// inmultim relatia cu c / d 
        /// z = c / d * x 
        /// t = c / d * y
        /// a * x + b * y = d
        /// fie x0 si y0 a.i.
        /// b * x0 + (a % b) * y0 = d 
        /// a * x + b * y = d
        /// daca b = 0 atunci d = a, x = 1, y = 0 
        /// b * x0 + (a % b) * y0 = a * x + b * y 
        /// (a % b) * y0 = a * x + b * (y - x0)
        /// fie c = a / b 
        /// (a - b * c) * y0 = a * x + b * (y - x0)
        /// a * y0 - b * c * y0 = a * x + b * (y - x0)
        /// a * (y0 - x) = b * (c * y0 + y - x0)
        /// y0 - x = 0 --> x = y0 
        /// c * y0 + y - x0 = 0 
        /// y = x0 - c * y0 
        int x, y;
        euclid(a, b, x, y);
        x *= c / d;
        y *= c / d;
        fout << x << ' ' << y << '\n';
    }
    return 0;
}