Cod sursa(job #2239085)

Utilizator TincaMateiTinca Matei TincaMatei Data 9 septembrie 2018 00:37:12
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.23 kb
#include <bits/stdc++.h>

using namespace std;

template<typename T>
T lgput(T b, long long e) {
	T ac = 1;
	while(e > 0) {
		if(e % 2 == 1)
			ac = ac * b;
		e /= 2;
		b = b * b;
	}
	return ac;
}

int lgputm(int b, int e, int mod) {
	int ac = 1;
	while(e > 0) {
		if(e % 2 == 1)
			ac = (long long)ac * b % mod;
		b = (long long)b * b % mod;
		e /= 2;
	}
	return ac;
}

template<typename T>
T euclidExtins(T a, T b, T &x, T &y) {
	if(b == 0) {
		x = 1;
		y = 0;
		return a;
	} else {
		T x2, y2, d;
		d = euclidExtins(b, a % b, x2, y2);
		x = y2;
		y = x2 - a / b * y2;
		return d;
	}
}

int inverseFermat(int a, int mod) {
	return lgputm(a, mod - 2, mod);
}

template<typename T>
T gcd(T a, T b) {
	T r;
	while(b > 0) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

namespace Maths {
	int localModulo = 1;
};

void setModulo(int x) {
	Maths::localModulo = x;
}

template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}

struct IntModulo {
private:
	int val, MOD;
public:
	IntModulo():val(0) {
		MOD = Maths::localModulo;
	}
	IntModulo(int x) {
		MOD = Maths::localModulo;
		x = x % MOD;
		if(x < 0)
			x += MOD;
		val = x;
	}
	IntModulo(long long x) {
		MOD = Maths::localModulo;
		x = x % MOD;
		if(x < 0)
			x += MOD;
		val = x;
	}
	IntModulo(int x, int _MOD) {
		MOD = _MOD;
		x = x % MOD;
		if(x < 0)
			x += MOD;
		val = x;
	}

	operator int() const {return val;}
	IntModulo operator= (const int &x) {val = x; return *this;}
	IntModulo operator+ (const int &x) {return IntModulo(val + x);}
	IntModulo operator- (const int &x) {return IntModulo(val - x);}
	IntModulo operator* (const int &x) {return IntModulo((long long)val * x);}
	IntModulo operator/ (const int &x) {return *this * inverseFermat(x, MOD);}
	bool operator== (const int &x) {return val == x;}
	bool operator!= (const int &x) {return !(val == x);}
};

struct FactorialClass {
	int N, MOD;
	
	IntModulo *fact, *invfact, *inverse;

	FactorialClass(int _N, int _MOD) : N(_N) {
		MOD = _MOD;
		fact = new IntModulo[1+N];
		invfact = new IntModulo[1+N];
		inverse = new IntModulo[1+N];
		
		for(int i = 0; i <= N; ++i)
			fact[i] = invfact[i] = inverse[i] = IntModulo(0, MOD);

		fact[0] = 1;
		for(int i = 1; i <= N; ++i)
			fact[i] = (long long)fact[i - 1] * i % MOD;
		invfact[N] = inverseFermat(fact[N], MOD);
		for(int i = N - 1; i >= 0; --i)
			invfact[i] = (long long)invfact[i + 1] * (i + 1) % MOD;
		for(int i = 1; i <= N; ++i)
			inverse[i] = (long long)fact[i] * invfact[i - 1] % MOD;
	}

	IntModulo comb(int n, int k) { return fact[n] * invfact[k] * invfact[n - k]; }
	IntModulo perm(int n, int k) { return fact[n]; }
	IntModulo starsnbars(int n, int k) { return comb(n + k - 1, n); }
};

int inverseEuclid(int a, int mod) {
	int x, y;
	euclidExtins(a, mod, x, y);
	return IntModulo(x, mod);
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = fopen("euclid3.in");
	FILE *fout = fopen("euclid3.out");
#endif
	
	int t;
	long long a, b, c;
	fscanf(fin, "%d", &t);
	while(t--) {
		fscanf(fin, "%lld%lld%lld", &a, &b, &c);
		long long x, y, d;
		d = euclidExtins(a, b, x, y);
		if(c % d != 0)
			fprintf(fout, "0 0\n");
		else
			fprintf(fout, "%lld %lld\n", x * c / d, y * c / d);
	}

#ifdef HOME
	fclose(fin);
	fclose(fout);
#endif
	return 0;
}