BOJ 1629 곱셈 c++

백준 1629 곱셈 cpp

 

딱 두 가지를 이용.

 

a의 n 제곱 * a의 n 제곱 = a의 2n 제곱.

2의 58승 % 67이 4라면 2의 116승 % 67 은 16이라는 것.

 

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

using ll = long long;

ll a,b,c;

/*
    a의 2b 승을 c로 나눈 나머지는 == a의 b승을 c로 나눈 나머지의 제곱을 c로 나눈 나머지.
    expo가 1이 되면 (원래 expo가 1이었다면) 리턴값은 num 을 div로 나눈 나머지. - 탈출문
    expo가 2의 배수라면 (b를 2로 나눈 solve의 리턴값) * same % div
    expo가 2의 배수가 아니라면 (b를 2로 나눈 solve의 리턴값) * same % div * num % div
*/

ll solve(ll num, ll expo, ll div) {
    if (expo <= 1) {
        return  num % div;
    }
    ll solved = solve(num, expo/2, div);
    solved = solved * solved % div;
    if (expo % 2 == 0) {
        return solved;
    } else {
        return solved  * num % div;
    }  
}

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