[백준 / BOJ] 1629 곱셈

알고리즘 분류: 수학, 분할 정복, 재귀

문제 링크: www.acmicpc.net/problem/1629

1629번: 곱셈

• O(logb)로 구현하기 위해서는 수학의 거듭제곱의 규칙을 활용해야 한다.
• (a^b)% c == (a^b/2)% c * (a^b/2)% c이다.
• 매 번 지수(b)의 홀수 여부를 판별해서 a를 한번 더 곱해준다.
• 재귀를 도는 동안 b가 절반씩 줄어드므로 O(logb)라 할 수 있다.

#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>

#define ll long long
#define INF 1e9

using namespace std;

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

ll a, b, c;

ll go(ll a, ll b, ll c) {
    if(b == 0) return 1;
    ll ret = go(a, b/2, c);
    ret = ret * ret % c;
    if(b%2 == 0) return ret;
    return (ret * a) % c;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> a >> b >> c;
    cout << go(a, b, c);
    
    return 0;
}