和为 K 的倍数

课程自编 · 前缀和与余数

题目描述

给出一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$ 和正整数 $K$。统计有多少个非空连续子区间 $[l,r]$ 满足 $a_l+a_{l+1}+\cdots+a_r$ 是 $K$ 的倍数。

输入格式

第一行两个整数 $n,K$。第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$。

输出格式

输出一个整数，表示和为 $K$ 的倍数的非空连续子区间个数。

数据范围与约定

$1 \le n \le 2\times 10^5$，$1 \le K \le 10^5$，$1 \le a_i \le 10^9$。

样例输入

5 3
1 2 3 4 5

样例输出

7

样例说明

前缀和模 $3$ 的余数为 $0,1,0,0,1,0$。余数 $0$ 出现 $4$ 次，任取两个端点得到 $6$ 个区间；余数 $1$ 出现 $2$ 次，得到 $1$ 个区间。总数为 $6+1=7$。

说明

课程自编题，数据由 src/gen.py 生成。