我说白了：前缀和+同余。
前缀和不讲。
首先是暴搜方法。
枚举每一个 l,r (1≤l≤r≤n)l,r\ (1\le l\le r\le n)l,r (1≤l≤r≤n)，判断是否能被 MMM 整除。
代码（40pts）：
进阶方法：同余。
前置知识：若 a≡b(modm)a\equiv b \pmod ma≡b(modm)，则 m∣(a−b)m\mid(a-b)m∣(a−b)。
这样，如果一个数（ara_rar ）的前缀和与前面一个数（ala_lal ）的前缀和同余，说明 al+1+⋯+ara_{l+1}+\cdots+a_ral+1 +⋯+ar 能被 MMM 整除。
即用一个数组统计每个数除以 MMM 的余数，计算时前面有几个和这个数同余的答案就加多少。
当然如果这个数的前缀和能被 MMM 整除，也要计算。所以数组中余数为 000 的初始值要设置为 111。
代码（100pts）：
