← 返回题目列表

Codeforces · 1033/D

D. 除数

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

给你 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$。每个 $$$a_i$$$ 的除数在 $$$3$$$ 和 $$$5$$$ 之间。考虑 $$$a = \prod a_i$$$ — 所有输入整数的乘积。求 $$$a$$$ 的约数个数。由于这个数字可能非常大,因此打印它对质数 $$$998244353$$$ 的模。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 500$$$) — 数字的数量。

接下来的 $$$n$$$ 行包含一个整数 $$$a_i$$$ ($$$1 \leq a_i \leq 2\cdot 10^{18}$$$)。保证每个 $$$a_i$$$ 的因数数量在 $$$3$$$ 和 $$$5$$$ 之间。

互动

从技术角度来看,这个问题是交互式的。因此,不要忘记输出行尾并刷新输出。另外,不要阅读超出您需要的内容。要刷新输出,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

输出

打印单个整数 $$$d$$$ - 产品 $$$a_1 \cdot a_2 \cdot \dots \cdot a_n$$$ 模 $$$998244353$$$ 的除数数。

黑客输入

对于 hacks,需要以特殊格式提供输入。

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 500$$$) — 数字的数量。

接下来的 $$$n$$$ 行都包含 $$$a_i$$$ 的质因数分解。该行包含一个整数 $$$k_i$$$($$$2 \leq k_i \leq 4$$$)— $$$a_i$$$ 和 $$$k_i$$$ 整数的质因数 $$$p_{i,j}$$$($$$2 \leq p_{i,j} \leq 2 \cdot 10^{18}$$$),其中$$$p_{i,j}$$$ 是 $$$a_i$$$ 的第 $$$j$$$ 个素因子。

在向参赛者提供输入之前,计算 $$$a_i = \prod p_{i,j}$$$。请注意,每个 $$$p_{i,j}$$$ 必须是素数,每个计算出的 $$$a_i$$$ 必须满足 $$$a_i \leq 2\cdot10^{18}$$$ 并且除数必须在 $$$3$$$ 和 $$$5$$$ 之间。参赛者将仅获得 $$$a_i$$$,而不是其质因数分解。

例如,您需要使用此测试来获取第一个样本:

示例

输入 #1

3
9
15
143

输出 #1

32

输入 #2

1
7400840699802997

输出 #2

4

输入 #3

8
4606061759128693
4606066102679989
4606069767552943
4606063116488033
4606063930903637
4606064745319241
4606063930904021
4606065559735517

输出 #3

1920

输入#4

3
4
8
16

输出#4

10

注意

在第一种情况下,$$$a = 19305$$$。它的约数是 $$$1, 3, 5, 9, 11, 13, 15, 27, 33, 39, 45, 55, 65, 99, 117, 135, 143, 165, 195, 297, 351, 429, 495, 585, 715, 1287、1485、1755、2145、3861、6435、19305$$$ — 总计 $$$32$$$。

在第二种情况下,$$$a$$$ 有四个除数:$$$1$$$、$$$86028121$$$、$$$86028157$$$ 和 $$$7400840699802997 $$$。

在第三种情况下$$$a = 202600445671925364698739061629083877981962069703140268516570564888699 375209477214045102253766023072401557491054453690213483547$$$。

在第四种情况中,$$$a=512=2^9$$$,所以答案等于$$$10$$$。