アルゴリズムとデータ構造

バイナリ累乗法 (Binary Exponentiation)

3つの整数 x, n, および m が与えられるとき、 の結果を求める問題です。

入力

入力は1行で、x, n, m の3つの整数が与えられます (1 ≤ x, n, m ≤ )。

出力

の結果を出力してください。

例 (Examples)

Input
Output
2 10 5
4

説明 (Explanation)

  1. 2^10 = 1024 ⇒ 1024 mod 5 = 4
 

チュートリアル

与えられる数がとても大きい可能性があるため、計算時間を短縮するのが重要です。バイナリ累乗法 (Binary Exponentiation) は、大きなべき乗を効率的に計算できるアルゴリズムです。通常の方法（1から n までループして、そのたびに x を乗じる）よりも、乗算回数をかなり減らせるので高速に計算できます。
 
バイナリ累乗法は以下の数学的考え方に基づきます。n が偶数なら:
これにより、x^{n/2} を一度計算すれば、その結果を二乗して素早くべき乗を求められる仕組みです。アルゴリズムは次のようになります:
def binpow(x, n, m):
    if n == 0:                        # 基本ケース: x^0 = 1
        return 1
    if n % 2 == 0:                    # nが偶数の場合 => halfを計算して掛け合わせる
        half = binpow(x, n // 2, m)   # halfを計算する
        return (half * half) % m      # res = x^(n/2) * x^(n/2)

    # nが奇数の場合 => res = x * x^(n-1)
    return (x * binpow(x, n - 1, m)) % m
バイナリ累乗法を使うことで、n を毎回2で割っていけるため、計算量は から へと大きく削減されます。n が奇数のときは一度乗算を行いますが、その後の再帰呼び出しでは n が偶数になるので、結果的に効率的な計算が可能です。
いくつかの入力例でアルゴリズムをシミュレートしてみましょう:
x = 2, n = 10（簡単のため m は省略）
  1. [n = 10] → n % 2 == 0 ⇒ binpow(2, 5) を計算
  1. [n = 5] → n % 2 ≠ 0 ⇒ 2 * binpow(2, 4) を返す
  1. [n = 4] → n % 2 == 0 ⇒ binpow(2, 2) を計算
  1. [n = 2] → n % 2 == 0 ⇒ binpow(2, 1) を計算
  1. [n = 1] → n % 2 ≠ 0 ⇒ 2 * binpow(2, 0) を返す
  1. [n = 0] → n == 0 ⇒ 1 を返す
  1. [n = 1 へ戻る] ⇒ 2 * 1 = 2
  1. [n = 2 へ戻る] ⇒ 2 * 2 = 4
  1. [n = 4 へ戻る] ⇒ 4 * 4 = 16
  1. [n = 5 へ戻る] ⇒ 2 * 16 ⇒ 32
  1. [n = 10 へ戻る] ⇒ 32 * 32 = 1024
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue