C++で関数 Y = (X^6 + X^2 + 9894845) % 971 の値を効率的に求める方法

問題概要

次のような関数が与えられます。

f(x) = (x⁶ + x² + 9894845) % 971

任意の x の値に対して f(x) の値を求めるのが課題です。例えば x = 5 を入力した場合、出力は 469 になります。

アプローチ：繰り返し二乗法（バイナリ法）

x をそのまま6乗すると値が非常に大きくなり、64ビット整数でもオーバーフローする恐れがあります。そこで、べき乗の計算途中で都度剰余を取りながら値を小さく保つ「繰り返し二乗法」を利用します。この方法なら計算量は指数のビット数に比例する O(log e) で済み、大きな x に対しても高速かつ安全に計算できます。

アルゴリズムの手順

• power_mod() 関数を定義します。この関数は底（base）、指数（exponent）、法（modulus）の3つの引数を受け取ります。
• base := base mod modulus とする。
• result := 1 で初期化する。
• exponent > 0 の間、次の処理を繰り返します。
  • exponent が奇数の場合： result := (result × base) mod modulus
  • base := (base × base) mod modulus
  • exponent := exponent ÷ 2（1ビット右シフト）
• result を返します。
• main 側では次の式で最終結果を求めます。
  ((power_mod(n, 6, m) + power_mod(n, 2, m)) % m + 355) % m

なお、式中の定数 355 は 9894845 % 971 = 355 となる事前計算済みの剰余です。定数項をあらかじめ約分しておくことで、計算をシンプルにしています。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

lli power_mod(lli base, lli exponent, lli modulus) {
    base %= modulus;
    lli result = 1;
    while (exponent > 0) {
        if (exponent & 1)
            result = (result * base) % modulus;
        base = (base * base) % modulus;
        exponent >>= 1;
    }
    return result;
}

int main() {
    lli n = 654654, m = 971;
    cout << (((power_mod(n, 6, m) + power_mod(n, 2, m)) % m + 355) % m);
}

入力

n = 654654

出力

450

まとめ

このように、繰り返し二乗法を使えば大きな指数を持つべき乗の剰余も高速かつ安全に計算できます。競技プログラミングや暗号処理などでも広く使われる基本テクニックなので、実装パターンごと覚えておくと便利です。