[Baekjoon/C++] 1629번 - 곱셈

[백준] Baekjoon Online Judge

문제로 이동

 

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

 

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

---

풀이

#include <iostream>
using namespace std;

int main() {
    long long A, B, C;
    cin >> A >> B >> C;

    long long result = 1;

    while (B > 0) {
        if (B % 2 == 1) result = (result * A) % C;

        A = (A * A) % C;
        B /= 2;
    }

    cout << result << '\n';

    return 0;
}

A의 값을 제곱해서 연산 횟수를 줄이는 방식으로 코딩했다.

 

			*		*	* = result의 값 변경
B		10	5	2	1
result		0	2	2	10	(지수)
A		2	4	8	16	(지수)

A가 2이고 B가 10일 때를 예시로 한 경우이다. 정직하게 A를 B번 제곱하게 된다면 답을 구하는데 10번의 연산이 필요할 것이나 위의 방식으로 문제를 풀면 4번의 반복만이 필요하다는 것을 알 수 있다.