题目大意

题目要求找出整数数组 a 中的所有连续子数组 [L, R]，使得在这个子数组中恰好有 k 个元素能被 x 整除。

题目意思也比较简单重点我们看到思路。

思路

1. 关键点分析

• 由于我们要统计恰好 k 个能被 x 整除的数的区间，我们方便统计可以将 a 转化为一个二进制数组 b，其中：
  • b[i] = 1 表示 a[i] 能被 x 整除。

本题为2024年10月26日中国电信机考原题

题目内容

给定一个整数序列 $a$ ，以及 $2$ 个整数 $x$ ，$k$ 。

求出有多少区间$[L, R](L <= R)$，使得该区间中恰好有 $k$ 个$a_i(L <= i <= R)$满足 $a_i$ 能被 $x$ 整除。

时间限制：1000ms

内存限制：262mb

输入描述

$1 <= length(a), x <= 10^5$ $0 <= k <= 10^5$

输出描述

返回答案

样例1

输入

1 2 3 4
2 1

输出

6

说明

总共有 $6$ 个区间，满足恰好有 $1$ 个数被 $2$ 整除。

$[1,2],[1,3],[2,2],[2,3],[3,4],[4,4]$ 。