解説:#15 Multiple count

## 解説 愚直な方法は$O(NQ)$で間に合いません。 ここで$K$が入力で一回だけ与えられ、クエリによって変化しないことを考えると$B_i = (A_i$が$K$で割り切れるなら$1$、そうでないならば$0)$とすることで以下のような問題が解ければよいです。 各クエリについて$B$の$X_i$番目から$Y_i$番目の和を求めよ。 これは$B$について累積和を構築しておくことで各クエリ$O(1)$で答えることができます。 実装例は以下の通りです。std::cin/std::coutは遅く、今回のように入力量が多い場合はそれだけでTLEすることがあるので代わりにscanf/printfを使いましょう。 ``` #include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } int main() { int n = ri(), k = ri(); int a[n]; for (auto &i : a) i = ri(); int b_sum[n + 1]; b_sum[0] = 0; for (int i = 0; i < n; i++) b_sum[i + 1] = b_sum[i] + (a[i] % k == 0); int q = ri(); for (int i = 0; i < q; i++) { int x = ri() - 1; int y = ri(); printf("%d\n", b_sum[y] - b_sum[x]); } return 0; } ```