Cod sursa(job #694634)

Utilizator DSzprogDombi Szabolcs DSzprog Data 27 februarie 2012 22:26:06
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>

typedef long long int Long;

Long a, b, c, x, y;
void dombi_szabolcs_extends_euclid_algorithm(Long aa, Long bb) {
	Long ax = 1;
	Long bx = 0;
	while (bb) {
		Long cx = ax - aa / bb * bx;
		ax = bx;
		bx = cx;
		Long rr = aa % bb;
		aa = bb;
		bb = rr;
	}
	if (c % aa) {
		x = 0; y = 0;
	} else {
		x = ax * c / aa;
		if (b) {
			y = (c - a * x) / b;
		}
	}
}

int main() {
	FILE * in = fopen("euclid3.in", "rt");
	FILE * out = fopen("euclid3.out", "wt");

	Long num;
	fscanf(in, "%lld", &num);
	while (num--) {
		fscanf(in, "%lld%lld%lld", &a, &b, &c);
		dombi_szabolcs_extends_euclid_algorithm(a, b);
		fprintf(out, "%lld %lld\n", x, y);
	}

	fclose(in);
	fclose(out);
}