Cod sursa(job #3290432)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 30 martie 2025 18:29:10
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

long long ext_gcd(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	else {
		long long nx, ny, g;
		g = ext_gcd(b, a % b, nx, ny);
		x = ny;
		y = nx - a / b * x;
		return g;
	}
}

int main() {
	FILE* fin = fopen("euclid3.in", "r");
	FILE* fout = fopen("euclid3.out", "w");
	int T;
	fscanf(fin, "%d", &T);
	for (int t = 0; t < T; ++t) {
		long long a, b, c, x, y;
		fscanf(fin, "%d %d %d", &a, &b, &c);
		long long g = ext_gcd(a, b, x, y);
		if (c % g) {
			fprintf(fout, "%d %d\n", 0, 0);
		}
		else {
			x *= c / g;
			y *= c / g;
			fprintf(fout, "%d %d\n", x, y);
		}
	}
}