CF2176F Omega Numbers

对于给定的数字 $n$，定义函数 $\omega(n)$，表示数 $n$ 的素因数分解中不相同的质数的个数。 例如，$\omega(12) = \omega(2^2 \cdot 3) = 2$。$\omega(120) = \omega(2^3 \cdot 3 \cdot 5) = 3$。 对于一个由自然数组成的数组 $a$ 和自然数 $k$，定义 $\operatorname{f}(a, k) = \sum_{i < j} \omega(a_i \cdot a_j)^k$，对所有满足 $i < j$ 的情况求和。 现在给定一个长度为 $n$ 的自然数数组 $a$，和一个自然数 $k$，请计算 $\operatorname{f}(a, k)$ 对 $998\,244\,353$ 取模后的结果。

输入包含多组测试数据。第一行包含测试用例个数 $t$，$(1 \le t \le 10^4)$。每组测试数据描述如下： 每组测试数据的第一行包含两个整数 $n$ 和 $k$，$(1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9)$，分别表示数组 $a$ 的长度和幂的指数。 第二行包含 $n$ 个自然数 $a_1, a_2, \ldots, a_n$，$(1 \leq a_i \leq n)$，表示数组 $a$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出一行一个整数，表示函数 $\operatorname{f}(a, k)$ 对 $998\,244\,353$ 取模后的结果。

第一个测试用例的解释： 对于任意一对 $(i,j)$，乘积的 $\omega(x)$ 都是 $\omega(3^2) = 1$。共有 $6$ 个不同的 $(i,j)$ 对，指数为 $1$，最后的答案为 $6$。 第二个测试用例的解释： 第二个测试用例中，任意一对的乘积都是 $1$，因此其中质因数的个数为 $0$，答案也为 $0$。 第三个测试用例的解释： 考虑所有的 $(i, j)$ 对： - $(1,2)$：第 $1$ 个和第 $2$ 个数的乘积为 $1 \cdot 2$，$\omega(2) = 1$。 - $(1,3)$：第 $1$ 个和第 $3$ 个数的乘积为 $1 \cdot 3$，$\omega(3) = 1$。 - $(1,4)$：第 $1$ 个和第 $4$ 个数的乘积为 $1 \cdot 4$，$\omega(2^2) = 1$。 - $(2,3)$：第 $2$ 个和第 $3$ 个数的乘积为 $2 \cdot 3$，$\omega(2 \cdot 3) = 2$。 - $(2,4)$：第 $2$ 个和第 $4$ 个数的乘积为 $2 \cdot 4$，$\omega(2^3) = 1$。 - $(3,4)$：第 $3$ 个和第 $4$ 个数的乘积为 $3 \cdot 4$，$\omega(3 \cdot 2^2) = 2$。 在答案中，$\omega(x)$ 的值需要取平方，所有项加起来为 $1^2 + 1^2 + 1^2 + 2^2 + 1^2 + 2^2 = 12$。 由 ChatGPT 5 翻译