C - ロト2

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400

問題文

N 枚のカードが 1 列に並べられており、i(1 ≦ i ≦ N) 番目のカードには整数 A_i が書かれています。

この N 枚のカードを使ったロト 2 という宝くじがあります。 ロト 21 番から N 番までの番号から異なる 2 つの番号 i, \, j (i < j) を選び、選ばれた 2 つの番号のカードにそれぞれ書かれた値の積 A_i A_jK の倍数となるとき当選するというルールで行われます。

A_iA_jK の倍数となるような ij の組合せ (i, \, j) を良い組合せと呼ぶことにします。良い組合せは何通りあるか求めなさい。

制約

  • 1 ≦ N ≦ 200{,}000
  • 1 ≦ A_i ≦ 10^{9} (1 ≦ i ≦ N)
  • 1 ≦ K ≦ 10^{9}
  • A_i, \, K はいずれも整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2  A_N

出力

良い組合せの総数を 1 行に出力せよ。


入力例 1

4 6
1 3 2 6

出力例 1

4

(1, \, 4), \, (2, \, 3), \, (2, \, 4), \, (3, \, 4)4 通りが良い組合せです。


入力例 2

5 1
1 2 3 1 2

出力例 2

10

どのように 2 つの番号を選んでも良い組合せになります。


入力例 3

12 60
38 19 180 222 560 1000 7 99 845 3600 12 90

出力例 3

33