[C++] 백준 1629 - 곱셈

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

1629번: 곱셈

 

1. 입력

2,147,483,647 이하의 자연수 A B C

 

2. 출력

A를 B번 곱한 수를 C로 나눈 나머지(\(A ^ B\) mod C)

 

3. 풀이

문제의 핵심은 \(A ^ B\)를 구하는 것이다. 다만 자료형의 크기 때문에 일정 수 이상이 되면 오버플로가 발생하므로, C로 나눈 나머지를 구하는 모듈러 연산이 추가로 요구된다.

 

단순한 반복문이나 재귀함수를 이용한 구현을 유도하는 문제는 당연히 아니다. 문제와 같은 거듭제곱 후 모듈러 연산은 대표적으로 RSA 알고리즘과 같은 암호학 분야에서 많이 사용되는데, 암호 알고리즘에 이러한 단순 구현을 적용하기에는 무리가 있다.

 

여러 방법이 있겠으나 나는 다음 두 가지를 이용했다.

1. 모든 자연수는 \(2 ^ n\)(n = 자연수)의 합으로 표현될 수 있다.
2. \(x ^ {N+M} = x ^ N \times x ^ M\)이다.

 

두 가지를 종합해 보면, y가 자연수라면 y는 \(2^n\)(n = 자연수)의 합으로 표현될 수 있으며, \(x^y\)는 \(x^{2^n}\)들의 곱으로 표현될 수 있다는 결론을 도출할 수 있다.

 

예를 들어 자연수 27은 16 + 8 + 2 + 1, 즉 \(2 ^ 4 + 2 ^ 3 + 2 ^ 1 + 2 ^ 0\)으로 표현될 수 있다.

 

즉, 자연수 27(\(00011011_{(2)}\))은 다음 이진수의 합으로 나타낼 수 있다.

 

\[ \begin{align}00010000_{(2)} \\
  + 00001000_{(2)} \\
  + 00000010_{(2)} \\
  + 00000001_{(2)} \\
\hline  = 00011011_{(2)} \end{align} \]

 

 \(x ^ {27}\)은 \(x^{2^4} \times x^{2^3} \times x^{2^1} \times x^{2^0}\)으로 표현될 수 있으므로, \(x^{27}\)은 \(x\)를 위의 각 이진수만큼 거듭제곱한 값의 곱과 같다.

 

 

정리하여 위 1629 문제에 대입해 보면, B를 2진수로 변환했을 때 1을 출력하는 비트의 각 자릿수를 n이라고 하면, \(2^n\)만큼 A를 거듭제곱 한 값을 모두 곱하면 \(A^B\)가 나온다는 것을 알 수 있다. 즉 B를 2진수로 변환한 뒤 각 자릿수가 1인지 확인하고, 그 자릿수에 해당하는 차수만큼 A를 거듭제곱 해주면 되는 것이다.

 

 

종합해 보면, 구현할 것은 다음과 같이 정리된다.

 

1. \(B_{(2)}\)를 한 칸 오른쪽으로 bit shift하고, 1과 AND 연산한다.

1-1. 참일 경우 value에 \(A\)를 곱한다.

2. \(A\)에 \(A^2\)을 대입한다.

3. B가 0이 될 때까지 2~3을 반복한다.

 

이제 구현할 것이 정리됐으니 구현할 일만 남았는데, 문제에서는 오버플로 방지를 위해 모듈러 연산을 요구하고 있으므로 2-1과 3에 모듈러 연산을 추가해야 한다.

 

또한 입력값은 2,147,483,647 이하의 값을 전제로 하고 있으므로, 변수 및 반환값 타입에서 오버플로가 발생하지 않도록 각별히 유의해야 한다. (아무리 생각해도 맞을 것 같은 문제를 제출해도 틀렸다는 메세지가 계속해서 나와서 처음부터 다시 살펴보니, 반환 타입을 typedef로 재정의 하는 과정에서 일부 변수의 타입을 수정하지 않아 오버플로가 발생해 생기는 문제였다.)

 

최종적으로 아래와 같이 구현했다.

 

#include <iostream>
#include <cmath>

typedef unsigned int RETURN_TYPE;
RETURN_TYPE PowAndMod(RETURN_TYPE x, RETURN_TYPE y, RETURN_TYPE m);

int main()
{
    RETURN_TYPE n, e, m;
    std::cin >> n >> e >> m;

    RETURN_TYPE result = PowAndMod(n, e, m);
    std::cout << result;
}

RETURN_TYPE PowAndMod(RETURN_TYPE x, RETURN_TYPE y, RETURN_TYPE m)
{
	RETURN_TYPE value = 1;

	while (y > 0)
	{
		if (y & 1)
			value = value * x % m;
		x = x * x % m;
		y >>= 1;
	}

	return value;
}