백준/1629번/곱셈/실버1

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

문제 설명

Site: Baekjoon
Number: 1629
Category: Divide and Conquer
Rank: Silver 1

지수 법칙과 모듈러 법칙을 활용하여 해결하는 문제이다.

지수 법칙 (짝수인 경우와 홀수인 경우)

모듈러 법칙

재귀 함수를 이용하여 지수부를 2씩 나누어 해결해야 시간초과가 발생하지 않는다.

#include <iostream>

using namespace std;

long long A, B, C;

long long Recursive(long long B)
{
    if (B == 0)
        return 1;
    if (B == 1)
        return A % C;

    long long n = Recursive(B / 2) % C;

    if(B % 2 == 0)
		return n * n % C;

    return (n * n % C * A % C) % C;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> A >> B >> C;

    long long ans = Recursive(B);

    cout << ans;

    return 0;
}