Submission #8410

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
8410	2014-09-13T17:28:48 Z	tncks0121	Quaternion inverse (kriii2_Q)	C++	0 / 4	0 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[i][j] != 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

0.0 / 1.0

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

Subtask #2

0.0 / 3.0

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