백준 10909번: Quaternion inverse

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

10909번: Quaternion inverse

---

사원수, quaternion이라는 낯선 대상이 주어졌을 뿐, 실제로는 복소수의 역원을 구하는 것과 크게 다르지 않습니다.

 

일반적인 사원수에 대해 역수를 구하는 방법은 다음 링크 와 같이 주어집니다. 다시 말하면, 다음 식이 성립합니다.

$$ < a+bi+cj+dk > \times < a-bi-cj-dk > = a^{2} + b^{2} + c^{2} + d^{2} $$

이 문제에서 주어지는 것이

$$ < a+bi+cj+dk > $$

이므로, 구해야하는 것은

$$ \frac{a}{a^{2}+b^{2}+c^{2}+d^{2}} + \frac{-b}{a^{2}+b^{2}+c^{2}+d^{2}}i + \frac{-c}{a^{2}+b^{2}+c^{2}+d^{2}}j + \frac{-d}{a^{2}+b^{2}+c^{2}+d^{2}}k $$

입니다.

 

한편 문제에서는 제한된 사원수라는 표현이 등장하는데, 위 사원수의 각 성분을 $\mathbb{Z}/p\mathbb{Z}$ 에서 구하라는 뜻입니다.

 

나눗셈을 처리하기 위해 modular multiplicative inverse의 존재성을 먼저 생각한다면, 분모와 $M$이 서로소이기만 하면 역원은 존재합니다.

 

역원이 존재한다면, 그 역원은 Fermat's little theorem으로 빠르게 구할 수 있고, 미리 약분을 하거나 별도의 공정을 가할 필요는 없으므로 풀이는 여기서 끝입니다. (스페셜 저지 문제이므로 음수를 따로 처리해줄 필요도 없습니다.)

 

제 코드는 다음과 같습니다.

#include <stdio.h>

long long power_modular (long long x, long long y, long long M);

int main() {
	
	long long M, T;
	scanf("%lld %lld", &M, &T);
	while(T--)
	{
		long long A, B, C, D;
		scanf("%lld %lld %lld %lld", &A, &B, &C, &D);
		
		long long absolute = A * A + B * B + C * C + D * D;
		if (absolute < M || absolute % M)
		{
			long long inv = power_modular(absolute % M, M - 2, M);
			
			A = A * inv % M;
			B = -B * inv % M;
			C = -C * inv % M;
			D = -D * inv % M;
			
			printf("%lld %lld %lld %lld\n", A, B, C, D);
		}
		else
		{
			printf("0 0 0 0\n");
		}
	}
	return 0;
}

long long gcd (long long A, long long B) {
	while(B) {
		long long temp = A % B;
		A = B;
		B = temp;
	}
	return A;
}

long long power_modular (long long x, long long y, long long M) {
	long long result = 1;
	while (y) {
		if (y % 2) {
			result = result * x % M;
		}
		x = x * x % M;
		y /= 2;
	}
	return result;
}

(C11, 140ms, 1116KB, 제출번호 55850415)

---

인풋이 많기 때문에 fast input을 사용하면 시간을 단축할 수 있습니다. (92ms, 55850834) unsigned type을 써도 약간 더 빨라집니다. (84ms, 55849423)