C - ロト2
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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