合适数对（数据加强版）

题目描述

给定一个长度为 $n$ 的正整数数列 $a_{1}, a_{2}, \ldots, a_{n}$ 和一个正整数 $k_{\text {。 }}$ 请你判断共有多少个数对 $(l, r)$ 同时满足：

• $1\leq l < r \leq n$
• 存在一个整数 $x$ 使得 $a_{l} \times a_{r}=x^{k}$ 成立

输入格式

第一行包含两个整数 $n, k_{\text {。 }}$ 第二行包含 $n$ 个正整数 $a_{1}, a_{2}, \ldots, a_{n}$ 。

输出格式

一个整数，表示满足条件的数对的数量。

样例输入

6 3
1 3 9 8 24 1

样例输出

5

数据范围

所有测试点满足 $2 \leq n \leq 10^{6}， 2 \leq k \leq 100 ， 1 \leq a_{i} \leq 10^{7}$。