A16816 | Omega Numbers
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
对于给定的数字 $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$ 取模后的结果。
例如，$\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$。
每组测试数据的第一行包含两个整数 $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$ 取模后的结果。
输入输出样例
输入 #1
3 4 1 3 3 3 3 4 1 1 1 1 1 4 2 1 2 3 4
输出 #1
6 0 12
第一个测试用例的解释：
对于任意一对 $(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$。
对于任意一对 $(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$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？