1629번 곱셈

문제 링크

곱셈

문제 풀이

자연수 A를 B번 곱하는데 이를 C로 나눈 나머지를 푸는 문제이다. A, B, C는 2,147,483,647 이하의 자연수이므로 long long 타입으로 하고, 곱하는 횟수가 매우 크므로 이를 분할 정복으로 푼다. 만약 곱해야 하는 횟수가 홀수이면 $A\times solve(n-1)$처럼 하나를 따로 빼고 재귀 호출하고, 짝수이면 $solve(n/2)$를 두 번 곱하는 것과 같으니까 한 번만 재귀 호출하여 구하고 이를 제곱한다.

구현

#include <iostream>
using namespace std;
using ll = long long;

ll A, B, C;

ll solve(ll n) {
    if (n == 1) return A;
    if (n % 2 == 1) return (A * solve(n - 1)) % C;

    int ret = solve(n / 2) % C;
    return (ret * ret) % C;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> A >> B >> C;
    cout << solve(B);
    return 0;
}