Pythonで数値をn回連結した際の剰余（モジュラス）を効率的に求めるプログラム

ある数値 A が与えられたとします。このAを n回連結 して大きな数Xを生成し、そのXを m で割った余り（モジュラス）を求めるのが今回の課題です。

例えば、入力が A = 15、n = 3、m = 8 の場合を考えてみましょう。このとき生成される数値Xは「151515」となり、151515 mod 8 = 3 であるため、出力は 3 になります。

解法のアプローチ

連結後の数値は桁数が膨大になる可能性があるため、実際に文字列として連結してから計算するのは非効率です。そこで、数学的な性質を利用して直接剰余を計算します。手順は以下の通りです。

• Aが0の場合は、0を返す
• an := A
• c := Aの桁数
• c := 10^c（桁数に対応する10の冪乗）
• d := c − 1
• newmod := d × m
• val := (c ^ n mod newmod) − 1
• val := (val + newmod) mod newmod
• an := (an × val) mod newmod
• (an ÷ d) の切り捨て値を返す

なぜこの方法で求まるのか

Aをn回連結した数値Xは、等比数列の和として次のように表せます。

X = A × (c^n − 1) ÷ d　※ここで c = 10^桁数、d = c − 1

割り算を含む式はモジュロ演算と相性が悪いため、あらかじめ d × m を法として計算しておくことで、最後にdで割り切れる形に整えられます。これにより、巨大な連結数を実際に構築することなく、O(log n) の計算量で答えを導き出せるのです。

実装例

以下のPythonコードを見て、理解を深めましょう。

def solve(A, n, m):
   if A == 0:
      return 0
   an = A
   c = len(str(A))
   c = 10**c
   d = c - 1
   newmod = d * m
   val = pow(c, n, newmod) - 1
   val = (val + newmod) % newmod
   an = (an * val) % newmod
   return an // d

A = 15
n = 3
m = 8
print(solve(A, n, m))

ここではPythonの組み込み関数 pow(c, n, newmod) を使用しています。これは「cのn乗をnewmodで割った余り」を高速に計算してくれる便利な関数です。

入力

15, 3, 8

出力

3

このように、数値を実際に連結せずとも冪乗のモジュロ演算を活用すれば、非常に大きな連結数の剰余も瞬時に求めることができます。