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>×<a−bi−cj−dk>=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)
'분할 정복을 이용한 거듭제곱 > 정수 거듭제곱' 카테고리의 다른 글
백준 25028번: Fully Generate (0) | 2023.03.10 |
---|---|
백준 18151번: DivModulo (0) | 2023.02.28 |
백준 27299번: 헌내기 현철 (0) | 2023.02.12 |
백준 14679번: 영우와 '갓4' (0) | 2023.02.12 |
백준 9556번: 수학 숙제 (0) | 2023.01.28 |