C言語で配列内の指定範囲の積（剰余演算）を求める方法

配列 A、範囲の左端 L、右端 R、そして素数 P を入力として与え、L から R までの範囲内にある要素の総乗（積）を P で割った余りを計算して出力するのが本記事の課題です。

下図のように、配列の要素が並んでおり、左端の値 L は 2、右端の値 R は 6 です。プログラムはこの範囲内に含まれる要素の積を順次計算していきます。

入出力例

Input-:  A[] = { 1, 2, 3, 4, 5, 6 }
    P = 29  L = 2 R = 6
Output-: 24
Input-:  A[] = {1, 2, 3, 4, 5, 6},
    L = 2 R = 5 P = 113
Output-: 7

最初の例では、配列の 2 番目から 6 番目までの要素（2 × 3 × 4 × 5 × 6 = 720）を計算し、素数 29 で割った余りである 24 が出力されています。

プログラムで用いるアプローチ

• 整数型の配列、左端の値（L）、右端の値（R）、素数（P）を入力として受け取る
• 左端の値から右端の値まで配列の要素を走査する
• 掛け算の結果を一時変数に保持しながら更新していく
• 各ステップで素数 P を法とした剰余演算を行い、オーバーフローを防ぐ
• 最終的な結果を出力する

アルゴリズム

Start
Step 1 -> 積を計算する関数を宣言
    int calculateProduct(int A[], int L, int R, int P)
        変数 int i を宣言
            L = L - 1 と設定
            R = R - 1 と設定
        int ans = 1 を宣言
        ループ For i = L; i <= R; i++
            ans = ans * A[i] と設定
            ans = ans % P と設定
        End
        return ans
Step 2 -> main() 内で
    配列 int A[] = { 1, 2, 3, 4, 5, 6 } を宣言
    変数 int P = 29 を宣言
    変数 int L = 2, R = 6 を宣言
    A, L, R, P の結果を出力
Stop

C言語による実装例

#include <stdio.h>
int calculateProduct(int A[], int L,int R, int P) {
    int i;
    // 配列は0番目から始まる一方、
    // LとRは1番目から始まるため調整する
    L = L - 1;
    R = R - 1;
    int ans = 1;
    for ( i = L; i <= R; i++) {
        ans = ans * A[i];
        ans = ans % P;
    }
    return ans;
}
int main() {
    int A[] = { 1, 2, 3, 4, 5, 6 };
    int P = 29;
    int L = 2, R = 6;
    printf("%d\n", calculateProduct(A, L, R, P));
    return 0;
}

実行結果

24

補足：なぜ剰余演算が必要か

範囲が広くなると、要素の積は瞬く間に巨大な数になり、int 型などの固定幅整数ではオーバーフローが発生します。そこで各ステップで素数 P を法とした剰余を取ることで、中間結果を常に小さな値に抑えられます。また、剰余演算には分配法則が成り立つため、(a * b) % P = ((a % P) * (b % P)) % P のように各段階で余りを取っても最終結果は変わりません。