곱셈

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
int A, B, C, ans;
// 거듭제곱을 O(logN)으로 처리 가능해진다!
// a^n * a^n = a^2n
ll POW(ll a, ll b, ll c){
    /* base condition! */
    if(b == 1) return a%c;
    else{
        ll val = POW(a, b/2, c);
        val = val * val % c;
        if(b%2 == 0) return val;
        else return val*a%c;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> A >> B >> C;
    ans = POW(A,B,C);
    cout << ans;
    return 0;
}

• key point!
  : a^n * a^n = a^2n 이라는 곱셈의 특징을 재귀로 구현하는 것!
• 재귀
  • 재귀를 종료하는 base condition을 잘 정해야 한다
  • 함수의 return을 잘 정해야 한다