Cod sursa(job #2909513)

Utilizator BadBoyRADULICEA Constantin Dumitru Petre BadBoy Data 14 iunie 2022 01:43:34
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <math.h>

// https://infoarena.ro/problema/euclid3


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


int main() {
	std::ifstream fin("euclid3.in");
	std::ofstream fout("euclid3.out");
	int linii, a, b, c, d, x, y;

	fin >> linii;
	for (int i = 0; i < linii; i++)
	{
        x = 0;
        y = 0;
        d = 0;
        fin >> a >> b >> c;
        euclid_ext(a, b, &d, &x, &y);   // a * X + b * Y = c
        if (c % d == 0) {
            x = x * c / d;
            y = y * c / d;
        }
        else {
            x = 0;
            y = 0;
        }
        fout << x << " " << y << "\n";
	}



	fin.close();
	fout.close();

	return 0;
}