← 返回题目列表

AtCoder · tkppc4_1_n

N. 多个

中文机器翻译题面 查看原题

配点: 600 点

問題文

安道君生日太长了 N 序列 使用 A 呈现给我。他是 我喜欢数字 D ,所以我创建了序列 A 从里面 A_l,A_{l+1},\ldots ,A_r(1 \leq l \leq r \leq N) 的和与积 我试图找到 D 的倍数 (l,r) 的组合。求这种组合的数量。 请输出


制約

  • 所有输入均为整数。
  • 1 \leq N \leq 10^5
  • 1 \leq D \leq 10^9
  • 1 \leq A_i \leq 10^9

入力

输入是按以下格式从标准输入给出的。

N D
A_1 A_2 \ldots A_N

出力

数列 A 从里面 A_l,A_{l+1},\ldots ,A_r(1 \leq l \leq r \leq N) 的和与积 我试图找到 D 的倍数 (l, r) 的组合数。


入力例1

5 3
1 2 1 3 2

出力例1

4
(l,r) = (1,5),(2,4),(3,5),(4,4)可以得到第 4 满足条件。

入力例2

5 3
8 6 9 1 20

出力例2

6

入力例3

8 1
1 10 100 1000 10000 1000000 10000000 100000000

出力例3

36

作者: 安道 作为