백준 곱셈[1629]

재귀를 처음 접하다보면 조금 어려운 느낌이 있는데
곱셈 문제를 통해서 최대한 쉽게 풀어쓰려고 노력했다!!
어떻게 이런 코드가 나오게 되었는지 왜 이런 코드가 나오게 되었는지 중학교때 배운 수학적인 방법도 꽤나 사용한 것 같다 ㅋ

#include <queue>
#include <iostream>

using namespace std;
using ll = long long;

ll POW(ll a, ll b, ll m) {
    if(b==1) return a%m;
    ll val = POW(a,b/2,m);
    val = val*val%m;

    if(b%2==0) return val;
    return val*a%m;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    ll a,b,c; cin >> a >> b>> c;
    cout << POW(a,b,c);

}