Cod sursa(job #3233198)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 2 iunie 2024 19:16:14
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <tuple>

using namespace std;

// Function to perform the Extended Euclidean Algorithm
tuple<int, int, int> extended_gcd(int a, int b) {
    if (b == 0)
        return make_tuple(a, 1, 0);
    int g, x, y;
    tie(g, x, y) = extended_gcd(b, a % b);
    return make_tuple(g, y, x - (a / b) * y);
}

// Function to find one solution of the equation a * x + b * y = c
bool find_solution(int a, int b, int c, int &x0, int &y0, int &g) {
    tie(g, x0, y0) = extended_gcd(a, b);
    if (c % g != 0)
        return false;
    x0 *= c / g;
    y0 *= c / g;
    return true;
}

int main() {
    ifstream infile("euclid3.in");
    ofstream outfile("euclid3.out");

    if (!infile || !outfile) {
        cerr << "Error opening file" << endl;
        return 1;
    }

    int T;
    infile >> T;

    for (int i = 0; i < T; ++i) {
        int a, b, c;
        infile >> a >> b >> c;

        int x, y, g;
        if (find_solution(a, b, c, x, y, g)) {
            // Solution exists, adjust x and y to be within the desired range if necessary
            outfile << x << " " << y << endl;
        } else {
            // No solution exists
            outfile << "0 0" << endl;
        }
    }

    infile.close();
    outfile.close();

    return 0;
}