C++で配列の全要素の積をnで割った余りを効率的に求める方法

問題の概要

n個の要素からなる配列 A が与えられたとします。このとき、配列内のすべての要素を掛け合わせた値を n で割った余り（剰余）を求めて出力します。

例として、A = [100, 10, 5, 25, 35, 14]、n = 11 の場合を考えてみましょう。このときの出力は 9 となります。つまり、以下の計算が成り立ちます。

100 × 10 × 5 × 25 × 35 × 14 mod 11 = 9

解法のポイント：オーバーフローを避ける工夫

すべての要素を先に掛け合わせると、値が非常に大きくなり、整数型の範囲を超えてオーバーフローが発生する可能性があります。これを防ぐためには、次の手順で計算を行います。

1. 各要素について、まず n で割った余りを求める
2. その余りを現在の累積結果に掛ける
3. 掛け算の結果に対して再度 n で割った余りを取る

このように毎回剰余を取ることで、途中の計算値が常に n 未満に保たれ、オーバーフローを回避できます。これはモジュロ演算の性質「(a × b) mod n = ((a mod n) × (b mod n)) mod n」を利用した標準的なテクニックです。

C++での実装例

#include<iostream>
#include<algorithm>
using namespace std;

int getRemainder(int a[], int size, int n) {
    int mul = 1;
    for(int i = 0; i < size; i++){
        mul = (mul * (a[i] % n)) % n;
    }
    return mul % n;
}

int main() {
    int arr[] = {100, 10, 5, 25, 35, 14};
    int size = sizeof(arr)/sizeof(arr[0]);
    int n = 11;
    cout << "The remainder is: " << getRemainder(arr, size, n);
}

実行結果

The remainder is: 9

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、必要な追加メモリは定数のみで空間計算量は O(1) となります。大きな数値を扱う場合でも安全に剰余を求められる、シンプルかつ効率的な手法です。