Pythonで「1」をn個並べた数をmで割った余りを効率的に求める方法

2つの整数 n と m が与えられたとき、「1」を n 個並べた数(例：n = 4 なら 1111)を m で割った余りを求めます。

たとえば入力が n = 4、m = 27 の場合、出力は 4 になります。これは 1111 ÷ 27 の余りが 4 であるためです。

アプローチ

n が大きくなると、「1」を n 個並べた数は桁数が膨大になり、そのまま整数として扱うのは非現実的です。そこで、この種の数(レピュニット)が次の式で表せることを利用します。

R(n) = (10n − 1) / 9

つまり、R(n) mod m を求めるには、10ⁿ mod 9m を高速に計算できれば十分です。ここで法として 9m を使う理由は、10ⁿ は必ず 9 で割ると 1 余る数だからです。そのため、10ⁿ mod 9m の結果を 9 で整数除算すると、そのまま答えが得られます。

べき乗の高速な計算には繰り返し二乗法(バイナリ法)を使用します。これは指数を2進数として分解しながら平方を繰り返すことで、計算量を O(log n) に抑える定番の手法です。

アルゴリズムの手順

• 関数 util(x, n, m) を定義する。xⁿ mod m を繰り返し二乗法で計算して返す
• y を 1 で初期化する
• n > 0 の間、次を繰り返す:
  • n が奇数なら、y = (y × x) mod m と更新する
  • x = (x × x) mod m と更新する
  • n を半分にする(右シフト)
• y を返す

メインの solve 関数では、util(10, n, 9 × m) の結果を 9 で整数除算して返します。

実装例

以下のコードで実際の動きを確認できます。

def util(x, n, m):
    y = 1
    while n > 0:
        if n & 1:
            y = (y * x) % m
        x = (x * x) % m
        n >>= 1
    return y

def solve(n, m):
    return util(10, n, 9 * m) // 9

n = 4
m = 27
print(solve(n, m))

入力

4, 27

出力

4

計算量

時間計算量は O(log n)、空間計算量は O(1) です。巨大な数を一度も生成しないため、n が非常に大きい場合でも高速かつ安定して動作します。