Submission #9369

#	Time	Username	Problem	Language	Result	Execution time	Memory
9369		corea	Quaternion inverse (kriii2_Q)	C++14	1 / 4	736 ms	9060 KiB

Q

#include <cstdio>
#include <tuple>
#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;
		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> quaternion(int a2, int b2, int c2, int d2, int a1, int b1, int c1, int d1) {
	return make_tuple(
		T(a1 * a2 - b1 * b2 - c1 * c2 - d1 * d2).value,
		T(a1 * b2 + b1 * a2 + c1 * d2 - d1 * c2).value,
		T(a1 * c2 - b1 * d2 + c1 * a2 + d1 * b2).value,
		T(a1 * d2 + b1 * c2 - c1 * b2 + d1 * a2).value
		);
}


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);

		auto it = quaternion((int)x[0].value, (int)x[1].value, (int)x[2].value, (int)x[3].value, a,b,c,d);
		if(it == make_tuple(1, 0, 0, 0)) {
			return make_tuple( (int)x[0].value, (int)x[1].value, (int)x[2]. value, (int) x[3].value );
		} else {
			return make_tuple(0, 0, 0, 0);
		}
	}
	catch(...) {
		return make_tuple(0, 0, 0, 0);
	}
}
void naive(int a, int b, int c, int d) {
	for(int x = 0; x < M; ++ x) {
		for(int y = 0; y < M; ++ y) {
			for(int z = 0; z < M; ++ z) {
				for(int w = 0; w < M; ++ w) {
					auto it = quaternion(x,y,z,w, a,b,c,d);
//					printf("? %d %d %d %d\n", get<0>(it), get<1>(it), get<2>(it), get<3>(it));
					if(it == make_tuple(1, 0, 0, 0)) {
						printf(">> %d %d %d %d\n", x, y, z, w);
						return;
					}
				}
			}
		}
	}
	printf( "0 0 0 0\n" );
}

void func(int a,int b, int c, int d ) {
	tie(a,b,c,d) = go(a,b,c,d);
	printf("%d %d %d %d\n", a, b, c, d);
}

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 );
	}

/*
	for( int a = 0; a < M; a ++ ) {
		for( int b = 0; b < M; b ++ ) {
			for( int c = 0; c < M; c ++ ) {
				for( int d = 0; d < M; d ++ ) {
					naive(a,b,c,d);
					func(a,b,c,d);
					printf( "\n" );
				}
			}
		}
	}
	*/
	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: 1 / 1
• Subtask 2: 0 / 3