제출 #9793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
9793		jaehadad	Quaternion inverse (kriii2_Q)	C++14	4 / 4	944 ms	1680 KiB

Q

#include<cstdio>
#include<cassert>
#include<cstring>
#include<map>
#include<set>
#include<time.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int M;

long pow(long long a, long long n, long long M) {
  long long ret = 1, unit = a % M;
  for(int y = 0; (1ll<<y) <= n; ++y) {
    if(n & (1ll << y)) 
      ret = (ret * unit) % M;
    unit = (unit * unit) % M;
  }
  return ret;
}

long long mod_inverse(long long a, long long M) {
  return pow(a, M-2, M);
}

vector<int> eliminate(vector<vector<int> >& A, vector<int>& b) {
  int n = A.size();
  for(int y = 0; y < n; ++y) {
    for(int y2 = y; y2 < n; ++y2) {
      if(A[y2][y]) {
        if(y != y2) {
          swap(A[y], A[y2]);
          swap(b[y], b[y2]);
        }
        break;
      }
    }
    if(A[y][y] == 0) return vector<int>();

    long long div = mod_inverse(A[y][y], M);
    for(int x = y; x < n; ++x)
      A[y][x] = (A[y][x] * div) % M;
    b[y] = (b[y] * div) % M;

    for(int y2 = y+1; y2 < n; ++y2) {
      long long mult = A[y2][y];
      for(int x = y; x < n; ++x)
        A[y2][x] = (A[y2][x] - (A[y][x] * mult) % M + M) % M;
      b[y2] = (b[y2] - (b[y] * mult) % M + M) % M;
    }
  }

  for(int y = n-1; y >= 0; --y) {
    for(int y2 = y-1; y2 >= 0; --y2) {
      long long mult = A[y2][y];
      for(int x = y; x < n; ++x) 
        A[y2][x] = (A[y2][x] - (A[y][x] * mult) % M + M) % M;
      b[y2] = (b[y2] - (b[y] * mult) % M + M) % M;
    }
  }

  return b;
}

int main() {
  int t;
  cin >> M >> t;
  for(int cc = 0; cc < t; ++cc) {
    vector<vector<int> > A;
    {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      A.push_back(vector<int>{a, -b, -c, -d});
      A.push_back(vector<int>{b, a, -d, c});
      A.push_back(vector<int>{c, d, a, -b});
      A.push_back(vector<int>{d, -c, b, a});
    }
    vector<int> b = { 1, 0, 0, 0 };
    // for(int i = 0; i < 4; ++i) {
    //   for(int j = 0; j < 4; ++j) {
    //     printf("%d ", A[i][j]);
    //   }
    //   printf("\n");
    // }
    vector<int> sol = eliminate(A, b);
    if(sol.empty())
      printf("0 0 0 0\n");
    else
      printf("%d %d %d %d\n", sol[0], sol[1], sol[2], sol[3]);
  }

}

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