곱셈 1629

문제

접근 방법

곧이곧대로 B번 곱하면 시간초과가 날 것이다.
분할 정복을 활용하여서 해결하면 된다.
2^8=4^4=8^2라는 것을 생각해보면 알듯이 절반에 해당하는 곱을 거듭하면 덜 계산하더라도 결괏값을 구할 수 있다.

코드

#include <iostream>
using namespace std;
int part(int A, int B, int C)
{
    if (B == 1)
        return A;
    long partVal = part(A, B / 2, C);
    long multiVal = (partVal * partVal) % C;
    if (B % 2)
        multiVal = (multiVal * A) % C;
    return multiVal;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int A, B, C;
    cin >> A >> B >> C;
    cout << part(A, B, C) % C;
    return 0;
}

풀이

B를 2로 나누면서 곱을 진행하면 된다. 만약 B가 홀수인 경우에는 별도로 A를 한 번 더 곱하면 된다.
11을 예로 들어서 확인해보면 된다.
A를 11번 곱한 값=(A를 5번 곱한 값)*(A를 5번 곱한 값)*A
A를 5번 곱한 값=(A를 2번 곱한 값)*(A를 2번 곱한 값)*A
A를 2번 곱한 값=A*A

하지만 조심해야 할 것이 하나 있었다.
B가 1인 경우이다. 그럴 경우 바로 반환되기에 C의 나머지가 아닌 값을 반환하게 된다.
출력하기 전에 C로 나머지 연산을 해주면 정답을 출력해준다.