백준 24009번: Huge Numbers (C++)

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

24009번: Huge Numbers

---

Solved By: Exponentiation By Squaring, Number Theory

 

거듭제곱은 시간 단축을 위해 분할 정복을 이용했습니다.

A, N, P가 주어지면 A의(N!) 제곱을 구하고, 이를 P로 나누라는 소리인데

 

우선, A의(N!)제곱은 N이 3이라 할 때,

(((A^1)^2)^3)과 같이 정리할 수 있습니다. 즉, 분할 정복을 이용한 거듭 제곱으로 각 제곱으로 도출된 값을 또다시 제곱하는 겁니다.

 

그리고 P로 나누는 것은 나머지 정리에 의하여 제곱 연산이 일어나는 곳마다 P로 나누는 값과 같으므로 오버 플로우가 일어나지 않게 모든 곱셈 연산에 P를 나눕니다.

>> (A * B) mod N == A mod N * B mod N

#include <iostream>
#define ll long long
using namespace std;

int t;

ll POW(ll a, ll b, ll c){
    if(b == 0) return 1;
    ll value = POW(a, b / 2, c);
    
    if(b % 2 == 0) return value * value % c;
    else return (value * value * a) % c;
}

ll factoPOW(ll a, ll b, ll c){
    if(b == 1) return a % c;
    else{
        ll res = a % c;
        for(int i = 2; i <= b; i++){
            res = POW(res, i, c);
            res %= c;
        }
        return res;
    }
}

int main(){
    cin >> t;
    for(int i = 0; i < t; i++){
        ll a, b, c; cin >> a >> b >> c;
        
        ll result = factoPOW(a, b, c);
        
        cout << "Case #" << i + 1 << ": ";
        cout << result << '\n';
    }
}