Processing math: 100%
본문 바로가기

분할 정복을 이용한 거듭제곱/정수 거듭제곱

백준 10909번: Quaternion inverse

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

 

10909번: Quaternion inverse

A가 주어질 때마다, AB=1을 만족하는 B=a+bi+cj+dk들 중 하나를 나타내는 네 개의 정수 a, b, c, d를 공백으로 구분하여 T 줄에 걸쳐 출력하면 된다. 만약 이런 B

www.acmicpc.net


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

 

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

<a+bi+cj+dk>×<abicjdk>=a2+b2+c2+d2

이 문제에서 주어지는 것이

<a+bi+cj+dk>

이므로, 구해야하는 것은

aa2+b2+c2+d2+ba2+b2+c2+d2i+ca2+b2+c2+d2j+da2+b2+c2+d2k

입니다.

 

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

 

나눗셈을 처리하기 위해 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)