Submission #9349

#	Time	Username	Problem	Language	Result	Execution time	Memory
9349		ainu7	Quaternion inverse (kriii2_Q)	C++98	4 / 4	784 ms	1676 KiB

Q

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

int mmod;
int inv_mod(int a, int b) {
  if (a < 0) return (mmod - inv_mod(-a, b)) % mmod;
  if (a == 1) return b;
  int div = mmod / a + 1;
  return inv_mod((a * (long long)div) % mmod, (b * (long long)div) % mmod);
}

int A[4][4], B[4];

void solve() {
  for (int i=0; i<4; i++) {
    int idx = -1;
    for (int j=i; j<4; j++)
      if (A[j][i]) idx = j;
    if (idx == -1) continue;
    for (int j=0; j<4; j++)
      swap(A[i][j], A[idx][j]);
    swap(B[i], B[idx]);

    int mm = inv_mod(A[i][i], 1);
    B[i] = (B[i] * (long long)mm) % mmod;
    for (int j=i; j<4; j++)
      A[i][j] = (A[i][j] * (long long)mm) % mmod;

    for (int j=0; j<4; j++) if (i != j) {
      B[j] = (B[j] - A[j][i] * (long long)B[i]) % mmod;
      if (B[j] < 0) B[j] += mmod;
      for (int k=3; k>=i; k--) {
        A[j][k] = (A[j][k] - A[i][k] * (long long)A[j][i]) % mmod;
        if (A[j][k] < 0) A[j][k] += mmod;
      }
    }
  }

  for (int i=0; i<4; i++)
    if (!A[i][i] && B[i]) {
      printf("0 0 0 0\n");
      return;
    }
  printf("%d %d %d %d\n", B[0], B[1], B[2], B[3]);
}

int main()
{
  int T;
  cin >> mmod >> T;

  for (int i=0; i<T; i++) {
    int a1, b1, c1, d1;
    cin >> a1 >> b1 >> c1 >> d1;
    A[0][0] = a1; A[0][1] = -b1; A[0][2] = -c1; A[0][3] = -d1;
    A[1][0] = b1; A[1][1] = a1; A[1][2] = -d1; A[1][3] = c1;
    A[2][0] = c1; A[2][1] = d1; A[2][2] = a1; A[2][3] = -b1;
    A[3][0] = d1; A[3][1] = -c1; A[3][2] = b1; A[3][3] = a1;

    B[0] = 1;
    B[1] = B[2] = B[3] = 0;
    solve();
  }
}

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