Cod sursa(job #3296972)

Utilizator christalknightChristian Micea christalknight Data 19 mai 2025 19:13:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
// https://infoarena.ro/problema/euclid3

#include <iostream>
#include <fstream>

using namespace std;

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

pair < long long int, long long int > solve_equation (long long int a, long long int b, long long int c);
void euclid_algorithm(long long int a, long long  int b, long long int* d, long long int* x, long long int* y); // Euclid's Algorithm 
// for finding x, y in the equation ax + by = d, where d is the highest common divisor of a and b

int main(){
    int t;
    long long int a, b, c; // coefficients of the equation
    pair < long long int, long long int > solution;

    fin >> t;

    while (t--) {
        fin >> a >> b >> c;
        solution = solve_equation(a, b, c);
        fout << solution.first << " " << solution.second << "\n";
    }

    fin.close();
    fout.clear();
    return 0;
}

pair < long long int, long long int > solve_equation (long long int a, long long int b, long long int c)
{
    long long int x = 0, y = 0;
    long long int highCommDiv = 0;

    euclid_algorithm(a, b, &highCommDiv, &x, &y);

    if (c % highCommDiv == 0) 
        return make_pair(x * c / highCommDiv, y * c / highCommDiv);
    else //if c is not divisible by the highest common divisor of a and b, the equation has no integer solutions
        return make_pair(1LL * 0, 1LL * 0); // typecast for safety
}

void euclid_algorithm(long long int a, long long int b, long long int* d, long long int* x, long long int* y)
{
    if (b == 0) { // trivial solution / base case, from which we construct the algorithm upwards (recursivley)
        *d = a;
        *x = 1;
        *y = 0;
    } 
    else {
        long long int x_0, y_0;
        euclid_algorithm(b, a % b, d, &x_0, &y_0); // algorithm for highest common divisor: (a, b) becomes (b, a % b) until a is divisable by b
        *x = y_0; // mathematical calcluations explained in the problem's resources, basically combining the base case with ax + by = d, 
        // we obtain x = y_0 and y = x_0 - (a / b) * y_0
        *y = x_0 - (a / b) * y_0;
    }
}