← 返回题目列表

AtCoder · nupc2024_e

E. 指数

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

配点 : 100 点

問題文

长度 小于或等于 N 整数序列 给出 A = (A_1, A_2, \dots, A_N) 和整数 可以获得第 M 。 对于
满足以下所有条件的一组整数 关于 (i,j,k) 的编号。 它是

  • 1\leq i,j,k \leq N
  • i, j, k 都不同
  • A_i \times M^{A_j}=A_k

制約

  • 3\leq N\leq 2\times10^5
  • 1\leq M\leq 10^{18}
  • 0\leq A_i\leq10^{18}
  • 所有输入均为整数

入力

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

N M
A_1 A_2 \dots A_N

出力

打印答案。 来自


入力例 1

5 2
1 2 4 8 16

出力例 1

6

满足条件 (i, j, k) 的组合如下 6 是的。 请注意,我们正在寻找除以

  • (1, 2, 3)
  • (1, 3, 5)
  • (2, 1, 3)
  • (3, 1, 4)
  • (3, 2, 5)
  • (4, 1, 5)

入力例 2

8 3
0 3 2 6 18 1 2 0

出力例 2

21

入力例 3

12 1
0 0 0 0 0 0 0 1 1 1 1 1

出力例 3

620