Submission #21419

#	Time	Username	Problem	Language	Result	Execution time	Memory
21419		gs14004	Quaternion inverse (kriii2_Q)	C++11	4 / 4	316 ms	2412 KiB

Q

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int inv[100005], mod;

vector<vector<int>> aug;
vector<int> sol;

void solve(){
	vector<int> basis[4];
	vector<int> sol2 = {0, 0, 0, 0};
	for(int i=0; i<4; i++){
		bool ok = 0;
		for(int j=0; j<4; j++){
			if(aug[i][j]){
				if(basis[j].empty()){
					basis[j] = aug[i];
					sol2[j] = sol[i];
					ok = 1;
					break;
				}
				else{
					int c = mod - 1ll * aug[i][j] * inv[basis[j][j]] % mod;
					for(int k=0; k<4; k++){
						aug[i][k] += 1ll * c * basis[j][k] % mod;
						aug[i][k] %= mod;
					}
					sol[i] += 1ll * c * sol2[j] % mod;
					sol[i] %= mod;
				}
			}
		}
		if(!ok && sol[i]){
			puts("0 0 0 0");
			return;
		}
	}
	for(int i=3; i>=0; i--){
		if(!basis[i].empty()){
			for(int j=i+1; j<4; j++){
				sol2[i] += mod - 1ll * basis[i][j] * sol2[j] % mod;
				sol2[i] %= mod;
			}
			sol2[i] = 1ll * sol2[i] * inv[basis[i][i]] % mod;
		}
	}
	for(int i=0; i<4; i++){
		printf("%d ", sol2[i]);
	}
	puts("");
}

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

int main(){
	int t;
	cin >> mod >> t;
	for(int i=1; i<mod; i++) inv[i] = ipow(i, mod-2);
	while(t--){
		int a, b, c, d;
		scanf("%d %d %d %d",&a,&b,&c,&d);
		aug = {{a, -b, -c, -d}, {b, a, -d, c}, {c, d, a, -b}, {d, -c, b, a}};
		sol = {1, 0, 0, 0};
		for(int i=0; i<4; i++){
			for(int j=0; j<4; j++){
				aug[i][j] += mod;
				aug[i][j] %= mod;
			}
		}
		solve();
	}
}

Compilation message (stderr)

Q.cpp: In function 'int main()':
Q.cpp:74:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&a,&b,&c,&d);
                                   ^

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