C++で積がkで割り切れる部分配列の数を数える

配列 arr[] と整数 k が与えられたとき、要素の積が k で割り切れる部分配列の個数を求める問題について解説します。ここでは、単純な全探索（ナイーブなアプローチ）と、セグメント木を用いて区間積を高速に取得するアプローチの2つを紹介します。

問題の例

例 1

入力: arr[] = {2, 1, 5, 8}, k = 4
出力: 4
説明: 条件を満たす部分配列は [8], [5,8], [1,5,8], [2,1,5,8] の4つ。

例 2

入力: arr[] = {7, 1, 9, 7}, k = 9
出力: 6
説明: [9], [9,7], [1,9], [1,9,7], [7,1,9], [7,1,9,7] の6つ。

ナイーブなアプローチ（全探索）

すべての部分配列の始点 i と終点 j を二重ループで列挙し、その区間の積を計算して k で割り切れるか判定します。計算量は O(n^3) となり、配列サイズが大きい場合には非現実的です。

実装例

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

// 部分配列の積がkで割り切れる個数を返す（ナイーブ版）
int countSubarraysNaive(const vector<int>& arr, int k) {
    int n = arr.size();
    int count = 0;
    for (int i = 0; i < n; ++i) {
        long long prod = 1; // オーバーフロー対策でlong longを使用
        for (int j = i; j < n; ++j) {
            prod *= arr[j];
            if (prod % k == 0) {
                ++count;
            }
        }
    }
    return count;
}

int main() {
    vector<int> arr = {2, 1, 5, 8, 10, 12};
    int k = 2;
    cout << "Count of subarrays whose product is divisible by k are: "
         << countSubarraysNaive(arr, k) << endl;
    return 0;
}

出力:

Count of subarrays whose product is divisible by k are: 18

セグメント木を用いたアプローチ

区間積のクエリを O(log n) で処理できるセグメント木を構築し、依然として全部分配列を列挙しますが、区間積の計算を高速化します。全体の計算量は O(n^2 log n) となり、ナイーブ版より高速ですが、依然として大規模データには不向きです。注意: この問題では、k の素因数分解と尺取り法（Two Pointers）または累積積とハッシュマップを用いた O(n log k) や O(n) 解法が存在し、実用的です。詳細は「より効率的な解法」を参照してください。

セグメント木の構築とクエリ

• 葉ノードには arr[i] % k を格納。
• 内部ノードには子ノードの積の % k を格納。
• 区間 [l, r] の積を % k で取得するクエリ関数を実装。

実装例

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

class SegmentTree {
    int n, k;
    vector<int> tree;
public:
    SegmentTree(const vector<int>& arr, int k_) : n(arr.size()), k(k_) {
        tree.assign(4 * n, 1);
        build(1, 0, n - 1, arr);
    }
    // 区間[l, r]の積 % k を取得
    int query(int l, int r) { return query(1, 0, n - 1, l, r); }
    int getK() const { return k; }
private:
    void build(int node, int left, int right, const vector<int>& arr) {
        if (left == right) {
            tree[node] = arr[left] % k;
            return;
        }
        int mid = (left + right) >> 1;
        build(node << 1, left, mid, arr);
        build(node << 1 | 1, mid + 1, right, arr);
        tree[node] = (int)((1LL * tree[node << 1] * tree[node << 1 | 1]) % k);
    }
    int query(int node, int left, int right, int ql, int qr) {
        if (qr < left || right < ql) return 1; // 単位元
        if (ql <= left && right <= qr) return tree[node];
        int mid = (left + right) >> 1;
        int leftProd = query(node << 1, left, mid, ql, qr);
        int rightProd = query(node << 1 | 1, mid + 1, right, ql, qr);
        return (int)((1LL * leftProd * rightProd) % k);
    }
};

int countSubarraysSegTree(const vector<int>& arr, int k) {
    int n = arr.size();
    SegmentTree st(arr, k);
    int count = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            if (st.query(i, j) == 0) ++count;
        }
    }
    return count;
}

int main() {
    vector<int> arr = {2, 1, 5, 8, 10, 12};
    int k = 2;
    cout << "Count of subarrays whose product is divisible by k are: "
         << countSubarraysSegTree(arr, k) << endl;
    return 0;
}

出力:

Count of subarrays whose product is divisible by k are: 18

より効率的な解法へのヒント

上記のセグメント木解法でも O(n^2 log n) です。制約が大きい場合（例: n ≤ 10^5）には、以下のアプローチで O(n log k) または O(n) が可能です。

1. kの素因数分解: k = p1^e1 * p2^e2 * ... と分解。
2. 各要素の寄与: 各 arr[i] が各素因数 p を何乗持つかを事前計算。
3. 尺取り法 / プレフィックス和 + マップ: 累積指数ベクトルを用いて、区間ごとの指数和が必要指数以上になる最小の左端を二分探索または尺取り法で求め、有効な部分配列数を累積。

この最適化により、大規模な入力でも高速に解けます。実装の詳細は応用編として別途学習することをお勧めします。