← 返回题目列表

AtCoder · ddcc_2016_qual_c

C. 乐透 2

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

配点 : 400 点

問題文

N 卡 1 按列排列, 第i(1 ≦ i ≦ N) 张牌是一个整数 写入 A_i 。

这个 使用 N 卡的乐透 有一种叫做 2 的彩票。 乐透 来自编号 2 是 它仅由 1 与 N 以内的数字不同 2 号码 i, \, j (i < j) 并选择 2 每张编号卡上所写值的乘积。 规则是当数字是 A_i A_j是 在 K 的倍数时,您就获胜。 使得它是

A_iA_j 是 在 K 的倍数 i 和 j 组合 我们将 (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