総和がkで割り切れる部分配列の個数を数える方法【C++実装付き】

はじめに

本記事では、「総和がkで割り切れる部分配列(サブ配列)の個数を求める」プログラムについて解説します。

具体的には、整数の配列と値kが与えられたとき、連続する部分配列のうち、その要素の合計がkで割り切れるものがいくつ存在するかを数えます。

アルゴリズムのポイント

すべての部分配列を素朴に調べるとO(n²)の計算量が必要になりますが、累積和(プレフィックスサム)と剰余演算を組み合わせることで、O(n + k)まで計算量を抑えられます。

考え方の核心は次の通りです。

• 先頭から順に累積和を計算し、それをkで割った余りごとに出現回数を記録する。
• 累積和の差が部分配列の総和に相当するため、同じ余りを持つ2つの累積和に挟まれた部分配列の総和は必ずkの倍数になる。
• よって、ある余りの出現回数をmとすると、その余りから生まれる部分配列の数は組合せの公式 m × (m − 1) / 2 で求められる。
• 加えて、先頭からその位置までの累積和自体がkで割り切れるケース(余りが0)は、それ単体で条件を満たすため、余り0の出現回数を答えに加算する。

なお、配列に負の数が含まれる場合でも ((cumSum % k) + k) % k とすることで、常に非負の正しい剰余を取得できます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

// 総和がkで割り切れる部分配列をカウントする
int count_subarray(int arr[], int n, int k){
    int mod[k];
    memset(mod, 0, sizeof(mod));
    int cumSum = 0;
    for (int i = 0; i < n; i++) {
        cumSum += arr[i];
        // 負の数にも対応できるよう、常に正の剰余を取る
        mod[((cumSum % k) + k) % k]++;
    }
    int result = 0;
    // 同じ余りを持つ累積和のペアを数える
    for (int i = 0; i < k; i++)
        if (mod[i] > 1)
            result += (mod[i] * (mod[i] - 1)) / 2;
    // 先頭からの累積和自体がkで割り切れる分を加算
    result += mod[0];
    return result;
}

int main(){
    int arr[] = { 4, 5, 0, -2, -3, 1 };
    int k = 5;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << count_subarray(arr, n, k) << endl;

    int arr1[] = { 4, 5, 0, -12, -23, 1 };
    int k1 = 5;
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << count_subarray(arr1, n1, k1) << endl;
    return 0;
}

実行結果

7
7

コードの解説

1つ目の入力 { 4, 5, 0, -2, -3, 1 }(k = 5)を例に挙げます。累積和は 4, 9, 9, 7, 4, 5 となり、これらを5で割った余りはそれぞれ 4, 4, 4, 2, 4, 0 です。

• 余り4が4回出現 → 4 × 3 / 2 = 6 通り
• 余り0が1回出現 → 配列全体 { 4, 5, 0, -2, -3, 1 } の総和5が該当 → 1通り

合計の 6 + 1 = 7 が答えとなります。2つ目の入力でも余りの分布が同じになるため、同様に7が出力されます。

まとめ

累積和の剰余に着目することで、総和がkで割り切れる部分配列の個数を線形時間で効率よく求められます。負の数を含む配列にも対応できる点も、この手法の大きな利点です。競技プログラミングやコーディング面接でも頻出のテクニックなので、ぜひマスターしておきましょう。