Submission #9613

#	Time	Username	Problem	Language	Result	Execution time	Memory
9613		hodduc	Quaternion inverse (kriii2_Q)	C++98	1 / 4	304 ms	1476 KiB

Q

#include<stdio.h>

int rev[100000];
int M, T;
int mult(int x, int e)
{
	if(e == 1) return x;
	long long tmp = mult(x, e>>1);
	tmp = (tmp * tmp) % M;
	if (e & 1) tmp = (tmp * x) % M;
	return (int)tmp;
}

void solve(int a,int b,int c, int d)
{
		long long f[4][4] = {
			{a,(M-b)%M,(M-c)%M,(M-d)%M},
			{b,a,(M-d)%M,c},
			{c,d,a,(M-b)%M},
			{d,(M-c)%M,b,a}
		};

		long long v[4] = {1,0,0,0};
		int vis[4];
		int ord[4];

		for(int t = 0; t < 4; t++) vis[t] = 0;
		for(int col = 0; col < 4; col++)
		{
			int row;
			for(row = 0; row < 4; row++) if(vis[row] == 0 && f[row][col] != 0) break;
			if(row == 4){
				ord[col] = -1;
				continue;
			}
			
			vis[row] = 1;
			ord[col] = row;

			int i, j;
			for(i = row; i == row; i++)
			{
				long long am = f[i][col];
				for(j = 0; j < 4; j++)
					f[i][j] = f[i][j] * rev[am] % M;
				v[i] = v[i] * rev[am] % M;
			}

			for(i = 0; i < 4; i++)
			{
				if(f[i][col] == 0) continue;
				if(i == row) continue;

				long long am = f[i][col];
				for(j = 0; j < 4; j++)
					f[i][j] = (f[i][j] - f[row][j] * am + M * M) % M;
				v[i] = (v[i] - v[row] * am + M * M) % M;
			}
		}

		int ass[4];
		int a2,b2,c2,d2;

		for(int i = 0; i < 4; i++)
		{
			if(f[i][0] == 0 && f[i][1] == 0 && f[i][2] == 0 && f[i][3] == 0 && v[i] != 0)
				goto FAIL;
		}

		for(int col = 0; col < 4; col++)
		{
			if(ord[col] == -1) {
				printf("0 ");
				continue;
			}
			int row = ord[col];
			int val = v[row] * rev[f[row][col]] % M;
			printf("%d ", val);
			ass[col] = val;
		}
		
		a2=ass[0], b2=ass[1], c2=ass[2], d2=ass[3];
		if ((a*a2-b*b2-c*c2-d*d2+M*M*4)%M != 1) printf("FAIL1 %d %d %d %d", a, b, c, d);
		if ((a*b2+b*a2+c*d2-d*c2+M*M*4)%M != 0) printf("FAIL2");
		if ((a*c2-b*d2+c*a2+d*b2+M*M*4)%M != 0) printf("FAIL3");
		if ((a*d2+b*c2-c*b2+d*a2+M*M*4)%M != 0) printf("FAIL4");
		printf("\n");
		return;
FAIL:
		printf("0 0 0 0\n");
		return;
}

int main()
{
	scanf("%d %d", &M, &T);
	rev[1] = 1;
	for(int i = 2; i < M; i++)
		rev[i] = mult(i, M-2);

	int a, b, c, d;
	while(T--){
		scanf("%d %d %d %d", &a, &b, &c, &d);
		solve(a,b,c,d);
	}
	return 0;
}

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