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

ここでは、配列の全要素を掛け合わせた結果をnで割った余り（剰余）を計算する方法を解説します。配列とnの値はユーザーから与えられるものとします。

例えば、配列が {12, 35, 69, 74, 165, 54} の場合、積は (12 × 35 × 69 × 74 × 165 × 54) = 19107673200 となります。この値を47で割った余りは14です。

一見するとこの問題は非常にシンプルです。すべての要素を掛け合わせてから、モジュロ演算子（%）を使えば答えが得られます。しかし、ここに落とし穴があります。積を計算する過程で、その値がint型やlong型の表現範囲を超えてしまう可能性があるのです。オーバーフローが発生すると、不正な結果が返されてしまいます。

この問題を回避するために、次のような手法を用います。ポイントは、掛け算を行うたびに余りを計算しておくことです。数学的には、(a × b) mod n = ((a mod n) × (b mod n)) mod n という性質が成り立つため、途中結果を常にn未満に保つことでオーバーフローを防げます。

アルゴリズム

multiplyRemainder(arr, size, n)

begin
    mul := 1
    for i in range 0 to size – 1, do
        mul := (mul * (arr[i] mod n)) mod n
    done
    return mul mod n
end

サンプルコード

#include<iostream>
using namespace std;
int multiplyRemainder(int arr[], int size, int n){
    int mul = 1;
    for(int i = 0; i<size; i++){
        mul = (mul * (arr[i] % n)) % n;
    }
    return mul % n;
}
int main(){
    int arr[6] = {12, 35, 69, 74, 165, 54};
    int size = 6;
    int n = 47;
    cout << "Remainder: " << multiplyRemainder(arr, size, n);
}

実行結果

Remainder: 14

このように、各要素について先にnで割った余りを求めてから掛け合わせ、さらにその都度mod nを適用することで、大きな数を扱わずに済みます。これにより、配列の要素数や要素の値が大きくても、int型の範囲内で安全に剰余を計算できます。