N - multiple Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 600 点

問題文

anmichiくんは誕生日に長さ 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

writer: anmichi