[BOJ] 백준 1629 - 곱셈

문제 링크

www.acmicpc.net/problem/1629

1629번: 곱셈

 

풀이

$a^b$를 $c$로 나눈 나머지를 출력해야 합니다.

거듭제곱을 단순하게 구현하면 $\text{O}(b)$의 시간 복잡도가 나오므로 적절히 최적화를 해줘야 합니다.

 

1) 만약 $b$가 홀수라면, $a^b = a\cdot a^{b-1}$ 입니다.

2) 만약 $b$가 짝수라면, $a^b = a^{b/2}\cdot a^{b/2}$ 입니다.

 

이런 식으로 짝수일 때 $b$의 범위를 반씩 줄여나가면 $\text{O}(\log b)$의 복잡도로 거듭제곱을 구현할 수 있습니다.

 

구현 시 주의사항이 있습니다. 재귀 함수로 구현할 때 $f(a, b/2)*f(a, b/2)$와 같이 함수를 호출하면 복잡도가 줄어들지 않습니다.

$f(a, b/2)$의 결과를 따로 저장해둔 뒤 그 값의 곱을 반환하도록 합시다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll a, b, m;

ll go(ll n, ll k) {
    if (k == 1) return n;
    if (k & 1) return n * go(n, k - 1) % m;
    ll res = go(n, k / 2);
    return res * res % m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b >> m;
    cout << go(a % m, b);
}