백준 10909 - Quaternion inverse [Python]

https://www.acmicpc.net/problem/10909

10909번: Quaternion inverse

 

사원수 \(a+bi+cj+dj\) 의 역원은 \(\frac{a-bi-cj-dj}{a^2+b^2+c^2+d^2}\) 이다.

이거에 mod 달면 그냥 답이 나오는데...  분모의 역원이 존재하지 않을 경우를 체크하지 않고 삽질함

 

import sys
input = sys.stdin.readline
 
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
 
def xgcd(a, b):
    if b == 0:
        return (1, 0, a)
    x, y, d = xgcd(b, a % b)
    return (y, x - (a // b) * y, d)
 
def inv(a, i):
    x, y, d = xgcd(a, i)
    return x
 
m, t = map(int, input().split())
while t:
    t -= 1
    a, b, c, d = map(int, input().split())
    n = (a*a+b*b+c*c+d*d)%m
    if gcd(n, m) > 1:
        print(0, 0, 0, 0)
        continue
    g = inv(n, m)
    print((a*g)%m, (-b*g)%m, (-c*g)%m, (-d*g)%m)