백준 곱셈 분할정도 1629

문제

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

문제 설명

분할정복이다 문제는 a를 b번 곱하고 수가 너무 크니 c로 % 하는 것이다..
(a % b) * (a % b) = 그래도 너무 크다...

그래서 분할정복을 통해서 100 -> 50 -> 25.. 이런식으로 가면된다
왜 ? 반반씩 줄어서 logn이지만 for로 하면 최대 21억번 ... 절대 안된다...

여기서 주의할점은 25 - > 12 , 12 1 하나 남으니 홀수 인 경우 * a로 한번 더 곱해주면된다

소스

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll a, b, c;

int solve(int a , int b) {
    if (b == 0) return 1; // n^0 == 1

    ll res = solve(a, b / 2);
    res = res * res % c;

    if (b % 2) res = res * a % c;

    return res;
}
int main() {

    cin >> a >> b >> c;
    cout << solve(a, b);
    return 0;
}

// a * b % m 
// (a % m) * (b % m) %m 

//power(a, b)
//a^b를 구하는 것이기에 예를 들면 a^4 = a^2 * a^2으로 가능하다 
//
//홀수인경우 -> a^5 = a^2 * a^2 * a ,, 1인경우 기저사례이므로 a,