Submission #9294

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9294	2014-09-28T05:24:25 Z	corea	Quaternion inverse (kriii2_Q)	C++14	0 / 4	0 ms	9056 KB

Q

#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>

long long M;
long long inv[1000001];

using namespace std;
 
#define REP(i, n) for(int i=0; i < n; ++i)
 
int n;

struct T {
	long long value;

	T(long long v = 0) {
		value = v;
		value += M;
		value %= M;
	}
	bool zero() const {
		return value % M == 0;
	}
};

T operator / (const T x, const T y) {
//	printf("> %lld %lld\n", x.value, y.value);
	if(y.value == 0) throw 0;
	return T((x.value * inv[(int)y.value]) % M);
}
T operator * (const T x, const T y) {
	long long v = x.value * y.value;
	v %= M;
	return T(v);
}
T& operator -= (T &v, const T r) {
	v.value -= r.value;
	v.value %= M;
	v.value+= M;
	v.value%= M;
	return v;
}

typedef vector<T> VD;
typedef vector< vector<T> > matrix;
 
void gauss(matrix A, VD b, VD &x) {
	int n = A.size(), m = A[0].size();
	vector<int> where(m, -1);

	for(int c=0, r=0; c<m && r<n; ++ c) {
		int pivot = r;
		for(int i = r; i < n; ++ i) {
			if(abs(A[i][c].value) > abs(A[pivot][c].value)) pivot = i;
		}
		if(A[pivot][c].zero()) continue;
		A[pivot].swap(A[r]);
		swap(b[pivot], b[r]);
		where[c] = r;
 
		REP(i, n) if(i != r) {
			T v = A[i][c] / A[r][c];
			for(int j = c; j < m; ++ j) A[i][j] -= A[r][j] * v;
			b[i] -= b[r] * v;
		}
		++ r;
	}
	x.assign(m, 0);
	REP(i, m) if(where[i] != -1) x[i] = b[where[i]] / A[where[i]][i];
}

tuple<int ,int, int, int> go(int a, int b, int c, int d) {

	matrix A(4, VD(4));
	A[0] = {a, -b, -c, -d};
	A[1] = {b, a, -d, c};
	A[2] = {c, d, a, -b};
	A[3] = {d, -c, b, a};

	VD B = VD {T(1), T(0), T(0), T(0)};
	VD x;
	
	try {
		gauss(A, B, x);
		return make_tuple( (int)x[0].value, (int)x[1].value, (int)x[2]. value, (int) x[3].value );
	}
	catch(...) {
		return make_tuple(0, 0, 0, 0);
	}
}

int main() {
	scanf("%lld", &M);

	inv[1] = 1;
	for(int i = 2; i < M; ++ i) {
		inv[i] = M - ((M/i) * inv[M % i] % M);
		assert( (inv[i] * i) % M == 1 );
	}

	int T;
	scanf("%d", &T);

	for(int i = 0; i < T; ++ i) {
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);
		tie(a,b,c,d) = go(a,b,c,d);
		printf("%d %d %d %d\n", a, b, c, d);
	}
	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	9056 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-