CF895B XK Segments

当 Vasya 吃完他那块披萨时，课程已经开始了。由于上课迟到，老师给 Vasya 出了一道有趣的题目。Vasya 有一个数组 $a$ 和一个整数 $x$。他需要找出不同的有序下标对 $(i, j)$ 的数量，使得 $a_i \leq a_j$，并且恰好有 $k$ 个整数 $y$ 满足 $a_i \leq y \leq a_j$ 且 $y$ 能被 $x$ 整除。 在本题中，只有当 $i$ 等于 $j$ 时，$(i, j)$ 和 $(j, i)$ 才认为是同一个对。例如，$(1,2)$ 不等于 $(2,1)$。

第一行包含三个整数 $n, x, k$（$1 \leq n \leq 10^5$，$1 \leq x \leq 10^9$，$0 \leq k \leq 10^9$），分别表示数组 $a$ 的大小，以及题目中的整数 $x$ 和 $k$。 第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的各个元素。

输出一个整数，表示满足条件的有序下标对的数量。

在第一个样例中，只有三个满足条件的下标对——$(1,2)、(2,3)、(3,4)$。 在第二个样例中，有四个满足条件的下标对——$(1,1)、(2,2)、(3,3)、(4,4)$。 在第三个样例中，所有的下标对 $(i, j)$ 都满足条件，所以答案是 $5 \times 5 = 25$。 由 ChatGPT 5 翻译