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

配列に含まれるすべての要素を掛け合わせた値（総乗）を、特定の数値 n で割った余りを求めたいケースは、競技プログラミングや暗号処理などの場面でよく登場します。本記事では、その計算を効率的かつ安全に実現するJavaプログラムを紹介します。

実装例

import java.util.*;
import java.lang.*;
public class Demo{
    public static int remainder(int my_arr[], int arr_len, int val){
        int mul_val = 1;
        for (int i = 0; i < arr_len; i++)
            mul_val = (mul_val * (my_arr[i] % val)) % val;
        return mul_val % val;
    }
    public static void main(String argc[]){
        int[] my_arr = new int []{ 35, 100, 69, 99, 27, 88, 12, 25 };
        int arr_len = 8;
        int val = 11;
        System.out.println("配列の全要素の積を11で割った余りは次のとおりです");
        System.out.println(remainder(my_arr, arr_len, val));
    }
}

出力結果

配列の全要素の積を11で割った余りは次のとおりです
0

プログラムの解説

Demo クラスの中には、remainder という静的メソッドが定義されています。このメソッドは、引数として受け取った整数配列を先頭から順番に走査し、各要素に対して剰余演算を適用しながら積を累積的に計算していきます。

ここで重要なのが、ループ内で毎回 % val を適用している点です。すべての要素を掛け終わってから最後に一度だけ余りを求めると、中間結果が int 型の範囲（約21億）を超えてオーバーフローを起こす恐れがあります。そこで、剰余演算の性質「(a × b) % m = ((a % m) × (b % m)) % m」を利用し、各ステップで余りを取りながら計算することで、大きな数でも安全に処理できるようになっています。

main メソッドでは、除数となる数値（val = 11）、対象の整数配列、そして配列の長さがそれぞれ定義されます。続いて、これら3つを引数として remainder メソッドを呼び出し、得られた結果をコンソールに出力しています。

今回の例では、配列 {35, 100, 69, 99, 27, 88, 12, 25} のうち 35 と 99 が 11 で割り切れるため、全体の積も必ず 11 の倍数となり、余りは 0 になります。