C/C++で配列の全要素の積をnで割った余りを求めるプログラム

配列乗算の問題では、与えられた配列の全要素の積を計算し、その積を指定された数値nで割った余りを求めます。具体的な例を使って見ていきましょう。

入力: arr[] = { 12, 35, 69, 74, 165, 54 }
      N = 47
出力: 14

解説

配列が {12, 35, 69, 74, 165, 54} の場合、全要素の積は次のように計算されます。

(12 × 35 × 69 × 74 × 165 × 54) = 19107673200

この積を47で割ると、余りは14になります。これが出力として期待される値です。

素朴なアプローチの課題

最も単純な考え方は、すべての要素を先に掛け合わせてからnで剰余を取ることです。しかし、このアプローチには重大な欠点があります。配列の要素数が多かったり、各要素の値が大きかったりすると、積が符号なし64ビット整数型の上限（2⁶⁴）を超えてしまい、オーバーフローによって誤った結果が返される可能性があるのです。

解決策：各ステップで剰余を取る

この問題は、剰余演算の基本的な性質を利用することで回避できます。

(a × b) % n = ((a % n) × (b % n)) % n

つまり、各要素を掛け合わせるたびにnの剰余を計算すれば、中間結果が常にn未満に保たれるため、巨大な積を実際に計算することなく、最終的な余りを正確に求めることができます。

アルゴリズムの手順

1. 結果を格納する変数 mul を 1 で初期化します。
2. 配列の各要素に対して、mul = (mul × (arr[i] % n)) % n を実行します。
3. すべての要素を処理した後の mul の値が、求める余りとなります。

C/C++での実装例

#include <stdio.h>

int main() {
    int arr[] = { 12, 35, 69, 74, 165, 54 };
    int len = 6;
    int n = 47;
    int mul = 1;
    for (int i = 0; i < len; i++)
        mul = (mul * (arr[i] % n)) % n;
    printf("余りは %d です\n", mul);
    return 0;
}

出力

余りは 14 です

計算量

• 時間計算量： O(L)（L は配列の長さ）― 各要素を一度だけ処理すればよいため、非常に効率的です。
• 空間計算量： O(1) ― 追加で必要なメモリは定数個の変数のみです。

このように、逐次的に剰余を取る手法を用いれば、積がどれほど大きな値になってもオーバーフローを気にせず、安全かつ効率的に余りを計算できます。競技プログラミングなどでも頻出するテクニックなので、ぜひ覚えておきましょう。