CF549F Yura and Developers

Yura 有 $k$ 名开发者，以及一个包含 $n$ 个任务的列表，任务编号从 $1$ 到 $n$。Yura 打算从中选择一些任务在本周完成。由于 Looksery 奇怪的习惯，所选的任务编号必须是一些连续整数，且数量不少于 $2$，也就是说，这些任务的编号形式为 $l,l+1,\ldots,r$，其中 $1\leq l < r \leq n$。 每个任务 $i$ 都有一个整数 $a_i$，表示完成第 $i$ 个任务所需的工时。开发者们并不自信，甚至害怕困难的任务。因此，Yura 决定亲自完成最难的那个任务（即所需工时最多的任务，如果有多个难度相同的最难任务，他会任意选择其中之一）。因此，如果选中的任务编号为 $[l,r]$，那么剩下的 $r-l$ 个任务就由开发者们自己完成。 每位开发者可以在任何一个任务上花费任意整数小时，但最终每个任务 $i$ 必须正好使用 $a_i$ 小时完成。 最后但同样重要的是，如果有开发者的工作时间多于其他人，就会有人生气。如果能将剩余任务在开发者之间平均分配，让每位开发者工作时间相同（Yura 分担的任务不计入），那么编号区间 $[l,r]$ 就被称为“好区间”。 例如，假设 Yura 选择的任务工时分别为 $a=[1,2,3,4]$，他有三名开发者。他亲自完成最难的第四个任务，开发者需要完成 $[1,2,3]$ 的任务。如果第一个开发者在第一个任务上工作 1 小时，又在第三个任务上工作 1 小时，第二个开发者在第二个任务上工作 2 小时，第三个开发者在第三个任务上工作 2 小时，则每个开发者都工作了 2 小时，任务也都完成了。又比如，如果第一个任务需要 2 小时而不是 1 小时，则无法平均分配工作。 除了工作以外，Yura 还喜欢解题。他想知道有多少对 $(l,r)$（$1\leq l

输入的第一行包含两个正整数 $n$ 和 $k$（$1 \leq n \leq 300000, 1 \leq k \leq 1000000$），分别表示任务数量和开发者数量。 第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^9$）。

输出一个整数，表示满足条件的 $(l,r)$ 对数。

在第一个样例中，有三个好区间： 1. $[1,3]$ —— 最难任务需要 $3$ 小时，剩下的任务需要 $1$ 和 $2$ 小时。第一个开发者在第一个任务上工作 1 小时，第二和第三个开发者负责第二个任务，每人 1 小时。每个开发者正好工作 1 小时。 2. $[1,4]$ —— 最难任务需要 $4$ 小时，剩下的任务需要 $1,2,3$ 小时。第一个开发者在第一个和第三个任务上各工作 1 小时，第二个开发者在第二个任务上工作 2 小时，第三个开发者在第三个任务上工作 2 小时。每个开发者正好工作 2 小时。 3. $[3,4]$ —— 最难任务需要 $4$ 小时，剩下的任务只有 $3$ 小时。让每个开发者工作 1 小时即可。 由 ChatGPT 5 翻译