Cod sursa(job #897539)

Utilizator cprogrammer1994Cprogrammer cprogrammer1994 Data 27 februarie 2013 21:10:52
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstring>
#include <cstdio>
#include <cmath>

struct Pair {
	long long a;
	long long b;
	Pair(long long a, long long b) {
		this->a = a;
		this->b = b;
	}
	Pair mod(long long d, Pair p) {
		return(Pair(a - d * p.a, b - d * p.b));
	}
};

int gcd(int a, int b) {
	while (b) {
		int c = a % b;
		a = b;
		b = c;
	}
	return(a);
}

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

	int n;
	fscanf(in, "%d", &n);
	for (int i = 0; i < n; ++i) {
		int x, y, z;
		fscanf(in, "%d%d%d", &x, &y, &z);
		int t = gcd(x, y);
		if (z % t) {
			fprintf(out, "0 0\n");
		} else {
			z /= t;
			x /= t;
			y /= t;

			Pair px(1, 0);
			Pair py(0, 1);
			while (y) {
				long long d = x / y;

				int w = x % y;
				x = y;
				y = w;

				Pair pw = px.mod(d, py);
				px = py;
				py = pw;
			}
			fprintf(out, "%lld %lld\n", px.a * z, px.b * z);
		}
	}

	fclose(in);
	fclose(out);
}