oj.uz

Submission #9233

# Submission time Handle Problem Language Result Execution time Memory
9233 2014-09-28T04:56:04 Z kcm1700 Quaternion inverse (kriii2_Q) C++14
4 / 4
 136 ms 1088 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

int mod;

pair<long long, long long> extended_gcd(long long a, long long b) {
    if (b == 0) return make_pair(1, 0);
      pair<long long, long long> t = extended_gcd(b, a % b);
        return make_pair(t.second, t.first - t.second * (a / b));
}

long long modinverse(long long a, long long m) {
    return (extended_gcd(a, m).first % m + m) % m;
}


int main(){
  int T;
  scanf("%d%d",&mod,&T);
  while(T-->0){
    long long a,b,c,d;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    long long tmp = (a*a+b*b+c*c+d*d) % mod;
    if (tmp == 0) {
      puts("0 0 0 0");
      continue;
    }
    tmp = modinverse(tmp, mod);
    a *= tmp;
    b *= -tmp;
    c *= -tmp;
    d *= -tmp;
    a %= mod; a += mod; a %= mod;
    b %= mod; b += mod; b %= mod;
    c %= mod; c += mod; c %= mod;
    d %= mod; d += mod; d %= mod;
    printf("%lld %lld %lld %lld\n", a,b,c,d);
  }
  return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Correct 0 ms 1088 KB Output is correct
4 Correct 0 ms 1088 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 1088 KB Output is correct
2 Correct 104 ms 1088 KB Output is correct
3 Correct 108 ms 1088 KB Output is correct
4 Correct 116 ms 1088 KB Output is correct
5 Correct 116 ms 1088 KB Output is correct
6 Correct 104 ms 1088 KB Output is correct
7 Correct 116 ms 1088 KB Output is correct
8 Correct 132 ms 1088 KB Output is correct
9 Correct 128 ms 1088 KB Output is correct
10 Correct 124 ms 1088 KB Output is correct
11 Correct 116 ms 1088 KB Output is correct
12 Correct 128 ms 1088 KB Output is correct
13 Correct 136 ms 1088 KB Output is correct
14 Correct 120 ms 1088 KB Output is correct
15 Correct 136 ms 1088 KB Output is correct