Submission #9334

#	Time	Username	Problem	Language	Result	Execution time	Memory
9334		myungwoo	Quaternion inverse (kriii2_Q)	C++14	4 / 4	392 ms	1476 KiB

Q

#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAXM 100005
typedef long long lld;

int M, T;
int A, B, C, D;
int inv[MAXM];

int get_inv(int n)
{
	int m = M-2, ret = 1, v = n;
	for (;m;m>>=1, v=(lld)v*v%M) if (m&1) ret = (lld)ret*v%M;
	return ret;
}

int main()
{
	int i, j, k;
	scanf("%d%d", &M, &T);
	for (i=1;i<M;i++) inv[i] = get_inv(i);
	while (T--){
		scanf("%d%d%d%d", &A, &B, &C, &D);
		int p[4][5] ={
				{A, -B, -C, -D, 1},
				{B, A, -D, C, 0},
				{C, D, A, -B, 0},
				{D, -C, B, A, 0}
		};
		for (i=0;i<4;i++) for (j=0;j<5;j++) p[i][j] = (p[i][j]+M)%M;
		for (i=0;i<4;i++){
			if (!p[i][i]){
				for (j=i;j<4;j++) if (p[j][i]) break;
				if (j == 4) break;
				for (k=0;k<5;k++) swap(p[i][k], p[j][k]);
			}
			int v = inv[p[i][i]];
			for (j=0;j<5;j++) p[i][j] = (lld)p[i][j]*v%M;
			for (j=0;j<4;j++) if (i != j){
				int r = p[j][i];
				for (k=0;k<5;k++){
					p[j][k] = (p[j][k]-(lld)p[i][k]*r%M+M)%M;
				}
			}
		}
		if (i < 4) puts("0 0 0 0"); // no answer
		else{
			int ans[4]={0, };
			for (i=0;i<4;i++) printf("%d ", p[i][4]);
			puts("");
		}
	}
}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3