문제

문제링크

해설

• A^B를 C로 나눈 나머지를 구해야 하는데, A, B, C 모두 범위가 약 21억입니다.
• O(log(N))으로 풀지 않으면 100% 시간초과에 걸리며, 중간과정에 int 범위를 넘기 때문에 A, B, C는 unsigned long long 자료형으로 선언해야 합니다.
• 아이디어가 떠오르지 않으면 풀 수 없는 문제입니다.
• 핵심 아이디어는
  • (A^B) % C 의 답은 (A^(B/2)) % C와 같으며
  • (A^(B/2)) % C는 (A^(B/4)) % C와 같으며
  • …
  • 이 과정을 반복하다보면 A % C와 같아지는 때가 온다는 것입니다.
• 즉, O(log_2(N))으로 해결할 수 있습니다.
• 재귀함수를 이용하면 코드량을 줄일 수 있습니다.
• 이때, B가 홀수일 때는 B/2 + B/2 + 1 = B 라는 점을 유의합니다.

코드

#include <iostream>
using namespace std;

using ull = unsigned long long;
ull A, B, C;

ull solve(ull a, ull b) {
    if (b == 1) return a % C;

    // Divide range into half -> log2(N)
    ull ret = solve(a, b / 2);
    ret = (ret * ret) % C;
    if (b & 1) ret = (ret * a) % C;
    
    return ret;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> A >> B >> C;
    cout << solve(A, B) << '\n';
    return 0;
}

소스코드 링크

결과