[백준] 1629번

💻 C++ 기반

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

✔️ 2의 2k승의 나머지를 구하려면 2의 k승의 나머지끼리 곱해서 몫으로 나누면 됨

#include <cstdio>

using namespace std;

long long recur(long long A, long long B, long long C)
{
    if (B == 1)
    {
        return A % C;
    }
    long long temp = recur(A, B / 2, C);
    temp = temp * temp % C;
    if (B % 2 == 0)
    {
        return temp;
    }
    else
    {
        return temp * A % C;
    }
}

int main()
{
    long long A, B, C;
    scanf("%lld %lld %lld", &A, &B, &C);
    printf("%lld", recur(A, B, C));
    return 0;
}