#include <cstdio>
#include <tuple>
#include <cassert>
#include <vector>
#include <algorithm>
long long M;
long long inv[1000001];
using namespace std;
#define REP(i, n) for(int i=0; i < n; ++i)
int n;
struct T {
long long value;
T(long long v = 0) {
value = v;
value %= M;
value += M;
value %= M;
}
bool zero() const {
return value % M == 0;
}
};
T operator / (const T x, const T y) {
// printf("> %lld %lld\n", x.value, y.value);
if(y.value == 0) throw 0;
return T((x.value * inv[(int)y.value]) % M);
}
T operator * (const T x, const T y) {
long long v = x.value * y.value;
v %= M;
return T(v);
}
T& operator -= (T &v, const T r) {
v.value -= r.value;
v.value %= M;
v.value+= M;
v.value%= M;
return v;
}
typedef vector<T> VD;
typedef vector< vector<T> > matrix;
void gauss(matrix A, VD b, VD &x) {
int n = A.size(), m = A[0].size();
vector<int> where(m, -1);
for(int c=0, r=0; c<m && r<n; ++ c) {
int pivot = r;
for(int i = r; i < n; ++ i) {
if(abs(A[i][c].value) > abs(A[pivot][c].value)) pivot = i;
}
if(A[pivot][c].zero()) continue;
A[pivot].swap(A[r]);
swap(b[pivot], b[r]);
where[c] = r;
REP(i, n) if(i != r) {
T v = A[i][c] / A[r][c];
for(int j = c; j < m; ++ j) A[i][j] -= A[r][j] * v;
b[i] -= b[r] * v;
}
++ r;
}
x.assign(m, 0);
REP(i, m) if(where[i] != -1) x[i] = b[where[i]] / A[where[i]][i];
}
tuple<int, int, int, int> quaternion(long long a2, long long b2, long long c2, long long d2, long long a1, long long b1, long long c1, long long d1) {
return make_tuple(
T(a1 * a2 - b1 * b2 - c1 * c2 - d1 * d2).value,
T(a1 * b2 + b1 * a2 + c1 * d2 - d1 * c2).value,
T(a1 * c2 - b1 * d2 + c1 * a2 + d1 * b2).value,
T(a1 * d2 + b1 * c2 - c1 * b2 + d1 * a2).value
);
}
tuple<int ,int, int, int> go(int a, int b, int c, int d) {
matrix A(4, VD(4));
A[0] = {a, -b, -c, -d};
A[1] = {b, a, -d, c};
A[2] = {c, d, a, -b};
A[3] = {d, -c, b, a};
VD B = VD {T(1), T(0), T(0), T(0)};
VD x;
try {
gauss(A, B, x);
auto it = quaternion((int)x[0].value, (int)x[1].value, (int)x[2].value, (int)x[3].value, a,b,c,d);
if(it == make_tuple(1, 0, 0, 0)) {
return make_tuple( (int)x[0].value, (int)x[1].value, (int)x[2]. value, (int) x[3].value );
} else {
return make_tuple(0, 0, 0, 0);
}
}
catch(...) {
return make_tuple(0, 0, 0, 0);
}
}
void naive(int a, int b, int c, int d) {
for(int x = 0; x < M; ++ x) {
for(int y = 0; y < M; ++ y) {
for(int z = 0; z < M; ++ z) {
for(int w = 0; w < M; ++ w) {
auto it = quaternion(x,y,z,w, a,b,c,d);
// printf("? %d %d %d %d\n", get<0>(it), get<1>(it), get<2>(it), get<3>(it));
if(it == make_tuple(1, 0, 0, 0)) {
printf(">> %d %d %d %d\n", x, y, z, w);
return;
}
}
}
}
}
printf( "0 0 0 0\n" );
}
void func(int a,int b, int c, int d ) {
tie(a,b,c,d) = go(a,b,c,d);
printf("%d %d %d %d\n", a, b, c, d);
}
int main() {
scanf("%lld", &M);
inv[1] = 1;
for(int i = 2; i < M; ++ i) {
inv[i] = M - ((M/i) * inv[M % i] % M);
assert( (inv[i] * i) % M == 1 );
}
/*
for( int a = 0; a < M; a ++ ) {
for( int b = 0; b < M; b ++ ) {
for( int c = 0; c < M; c ++ ) {
for( int d = 0; d < M; d ++ ) {
naive(a,b,c,d);
func(a,b,c,d);
printf( "\n" );
}
}
}
}
*/
int T;
scanf("%d", &T);
for(int i = 0; i < T; ++ i) {
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
tie(a,b,c,d) = go(a,b,c,d);
printf("%d %d %d %d\n", a, b, c, d);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
9060 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9060 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9060 KB |
Output is correct |
| 4 |
Correct |
16 ms |
9060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
576 ms |
9060 KB |
Output is correct |
| 2 |
Correct |
688 ms |
9060 KB |
Output is correct |
| 3 |
Correct |
696 ms |
9060 KB |
Output is correct |
| 4 |
Correct |
724 ms |
9060 KB |
Output is correct |
| 5 |
Correct |
696 ms |
9060 KB |
Output is correct |
| 6 |
Correct |
708 ms |
9060 KB |
Output is correct |
| 7 |
Correct |
704 ms |
9060 KB |
Output is correct |
| 8 |
Correct |
736 ms |
9060 KB |
Output is correct |
| 9 |
Correct |
728 ms |
9060 KB |
Output is correct |
| 10 |
Correct |
740 ms |
9060 KB |
Output is correct |
| 11 |
Correct |
736 ms |
9060 KB |
Output is correct |
| 12 |
Correct |
728 ms |
9060 KB |
Output is correct |
| 13 |
Correct |
744 ms |
9060 KB |
Output is correct |
| 14 |
Correct |
748 ms |
9060 KB |
Output is correct |
| 15 |
Correct |
728 ms |
9060 KB |
Output is correct |
