BOJ 1629 Problem Solution (Python)

This post was migrated from Tistory. You can find the original here.

Approach

A, B, and C can all be as large as the 32-bit int range (about 2.1 billion).

If we approach the problem directly,

X = (A ** B) % C

1. Multiplying A up to 2.1 billion times is too slow — the time complexity doesn’t work.

2. Raising a number that large to a power also raises overflow concerns.

Solution

Let’s solve it.

1. (Using exponent rules) Split the exponent to reduce the number of operations.

A**30 = (A**15)**2

A**15 = (A**7)**2 * A

A**7 = (A**3)**2 * A

A**3 = (A**1)**2 * A

A**1 = A

Generally, when the value is roughly halved at every step,

the number of steps needed to reach the end is expressed with logarithmic time complexity, O(log N).

100 → 50 → 25 → 12 → 6 → 3 → 1

log₂100 ≈ 6.64

Since each step down to 1 involves a squaring operation, the total number of operations is roughly 2 log N, plus one extra multiplication for each odd step (+ C).

So the total operation count can be approximated as O(2 log N + C) ≈ O(log N).

2. (Using modular arithmetic rules) Keep the maximum intermediate value around the level of C**2.

If we use a Long type (64-bit), it can represent values up to the square of the 32-bit max (about 2.1 billion), so we can bound the intermediate values to around C**2.

(A⋅B) mod M=((A mod M)⋅(B mod M)) mod M (multiplication property)

A**K mod M = ((A mod M)**K) mod M (exponentiation property)

A**30 mod M = (A**15)**2 mod M

A**15 mod M = ((A**7)**2 * A) mod M = (((A**7)**2)) * (A mod M)) mod M

A**7 mod M = ((A**3)**2 * A) mod M = …

A**3 mod M = ((A**1)**2 * A) mod M = …

A**1 mod M = A mod M

The maximum value of A**k mod M is M-1 (e.g., M = 2.1 billion, A = 2.1 billion − 1).
So squaring alone during the process isn’t a problem. However, when k is odd we need one extra multiplication by A, which can push the value up to roughly M**3.
Here, by applying the multiplication property and computing (M-1)**2 mod M first, the subsequent operation stays within (M-1) * A ≈ M**2.

Code

import sys

# a = base, b = exponent
def recur(a, b, c):
    if (b <= 2):
        return (a**b) % c

    # even
    if (b%2 == 0):
        return (recur(a, b//2, c)**2) % c
    # odd
    else:
        t = (recur(a, b//2, c)**2)
        return ((t%c) * (a%c)) % c

A, B, C = map(int, sys.stdin.readline().split())
print(recur(A, B, C))