【Python】配列の全要素の積をnで割った余りを求めるプログラムの書き方

本記事では、以下の問題に対する解決策について詳しく解説します。

問題文

複数の数値からなる配列と整数 n が与えられたとき、配列内のすべての要素を掛け合わせた結果を n で割った余りを出力する必要があります。

アプローチ

• まず、arr[i] % n のように各要素の余りを個別に計算します。次に、その余りを現在の結果に掛け合わせます。

• 掛け算を行うたびに再度剰余演算を適用することで、オーバーフローを回避できます。この手法は、モジュラー算術（合同式）の分配則に基づいています。

( a * b) % c = ( ( a % c ) * ( b % c ) ) % c

実装例

def findremainder(arr, lens, n):
    mul = 1
    # 各要素の余りを順に計算
    for i in range(lens):
        mul = (mul * (arr[i] % n)) % n
    return mul % n

# 実行コード
arr = [100,1,2,3,4,5,6,6,7]
lens = len(arr)
n = 11
print(findremainder(arr, lens, n))

出力結果

1

この例では、配列 [100, 1, 2, 3, 4, 5, 6, 6, 7] のすべての要素を掛け合わせた結果を 11 で割った余りとして「1」が出力されます。処理の流れとしては、各要素を 11 で割った余りを順番に累積的に掛け合わせ、その都度剰余を取ることで、巨大な数値になっても計算が破綻しない仕組みになっています。

まとめ

本記事では、配列の全要素の積を n で割った余りを効率的に求める方法について学びました。毎ステップで剰余を取ることでオーバーフローを防ぎ、大きな数値を扱う場合でも安全かつ高速に計算できる点がこの手法の大きなメリットです。