Submission #8411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
8411	2014-09-13T17:32:15 Z	tncks0121	Quaternion inverse (kriii2_Q)	C++	4 / 4	396 ms	1992 KB

Q

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h> 
#include <time.h>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
 
ll M;
int T;

ll inv[100005];

lf fpow (ll a, ll b) {
	ll ret = 1;
	while(b > 0) {
		if(b & 1) ret = (ret * a) % M;
		a = (a * a) % M;
		b >>= 1;
	}
	return ret;
}

int main() {
	scanf("%lld%d", &M, &T);
	assert(1 <= T && T <= 100000);
	for(int i = 2; i * i <= M; i++) assert(M % i != 0);

	for(int i = 1; i <= M; i++) inv[i] = fpow(i, M-2);

	while(T--) {
		ll a, b, c, d; scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		assert(0 <= a && a < M);
		assert(0 <= b && b < M);
		assert(0 <= c && c < M);
		assert(0 <= d && d < M);

		ll T[4][4] = {
		//   a2 b2 c2 d2
			{+a, -b, -c, -d},
			{+b, +a, -d, +c},
			{+c, +d, +a, -b},
			{+d, -c, +b, +a}
		};

		vector< vector<ll> > mat(4, vector<ll>(4));
		ll ans[] = {1, 0, 0, 0};

		for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) mat[i][j] = (T[i][j]+M)%M;

		for(int i = 0; i < 4; i++) {
			for(int j = i; j < 4; j++) {
				if(mat[j][i] != 0) {
					swap(mat[i], mat[j]);
					swap(ans[i], ans[j]);
					break;
				}
			}

			{
				ll t = mat[i][i];
				for(int k = 0; k < 4; k++) mat[i][k] = (mat[i][k] * inv[t]) % M;
				ans[i] = (ans[i] * inv[t]) % M;
			}

			for(int j = 0; j < 4; j++) if(i != j && mat[j][i] != 0) {
				ll t = mat[j][i];
				for(int k = 0; k < 4; k++) {
					mat[j][k] -= (mat[i][k] * t) % M;
					if(mat[j][k] < 0) mat[j][k] += M;
				}
				ans[j] -= (ans[i] * t) % M;
				if(ans[j] < 0) ans[j] += M;
			}
		}

		bool good = true;
		for(int i = 0; i < 4; i++) {
			ll w = 0;
			for(int j = 0; j < 4; j++) w = (w + ((M+T[i][j]) * ans[j]) % M) % M;
			if((i == 0 && w != 1) || (i > 0 && w != 0)) good = false;
		}

		if(!good) memset(ans, 0, sizeof ans);
		printf("%lld %lld %lld %lld\n", ans[0], ans[1], ans[2], ans[3]);
		
	}
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1992 KB	Output is correct
2	Correct	0 ms	1992 KB	Output is correct
3	Correct	0 ms	1992 KB	Output is correct
4	Correct	8 ms	1992 KB	Output is correct

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	272 ms	1992 KB	Output is correct
2	Correct	336 ms	1992 KB	Output is correct
3	Correct	332 ms	1992 KB	Output is correct
4	Correct	316 ms	1992 KB	Output is correct
5	Correct	360 ms	1992 KB	Output is correct
6	Correct	340 ms	1992 KB	Output is correct
7	Correct	344 ms	1992 KB	Output is correct
8	Correct	352 ms	1992 KB	Output is correct
9	Correct	360 ms	1992 KB	Output is correct
10	Correct	384 ms	1992 KB	Output is correct
11	Correct	388 ms	1992 KB	Output is correct
12	Correct	392 ms	1992 KB	Output is correct
13	Correct	388 ms	1992 KB	Output is correct
14	Correct	396 ms	1992 KB	Output is correct
15	Correct	388 ms	1992 KB	Output is correct