[백준 32981번] 찐 Even Number (C++)

문제링크 : https://www.acmicpc.net/problem/32981

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

const int MOD = 1000000007;

long long cal(long long base, long long exp, int mod) {
    long long result = 1;
    long long cur = base % mod;
    while (exp > 0) 
    {
        if (exp%2) result = (result * cur) % mod;
        cur = (cur * cur) % mod;
        exp /=2;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q; 
    cin >> Q;
    while(Q--) 
    {
        int N; cin >> N;
        long long ans = 0;
        if (N == 1) ans = 5;
        else ans = (4 * cal(5, N - 1, MOD)) % MOD;
        cout << ans << "\n";
    }

    return 0;
}

 

N=1의 경우 0도 가능하기에 총 5가지이다.

N=2 이후 부터는 맨 앞에 0이 불가능하므로 맨 앞은 4가지가 가능하다.

이후 자릿수에 대해서는 모두 가능하기에 5가지이다.

따라서 이를 식으로 표현하면 4 * pow(5, N-1)이다.

 

다만, 이를 그대로 적용하면 시간초과가 걸린다.

따라서 해당 식은 분할정복을 이용한 거듭제곱을 통한 계산으로 빠르게 처리해주어야 한다.