当前没有测试数据。

E - 白板上的最小公倍数

得分：500分

问题描述

白板上写有$N$个整数$a_1, \ldots, a_N$。
在这里，$a_i$可以表示为$a_i = p_{i,1}^{e_{i,1}} \times \ldots \times p_{i,m_i}^{e_{i,m_i}}$，其中$m_i$个素数$p_{i,1} \lt \ldots \lt p_{i,m_i}$和正整数$e_{i,1}, \ldots, e_{i,m_i}$。
你将选择其中一个整数将其替换为$1$。
找到在替换后，这$N$个整数的最小公倍数可能的取值个数。

约束

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq m_i$
• $\sum{m_i} \leq 2 \times 10^5$
• $2 \leq p_{i,1} \lt \ldots \lt p_{i,m_i} \leq 10^9$
• $p_{i,j}$是素数。
• $1 \leq e_{i,j} \leq 10^9$
• 输入中的所有数值都是整数。

输入

输入从标准输入中按照以下格式给出：

$N$

$m_1$

$p_{1,1}$ $e_{1,1}$

$\vdots$

$p_{1,m_1}$ $e_{1,m_1}$

$m_2$

$p_{2,1}$ $e_{2,1}$

$\vdots$

$p_{2,m_2}$ $e_{2,m_2}$

$\vdots$

$m_N$

$p_{N,1}$ $e_{N,1}$

$\vdots$

$p_{N,m_N}$ $e_{N,m_N}$

输出

打印答案。

4
1
7 2
2
2 2
5 1
1
5 1
2
2 1
7 1

3

白板上的整数是$a_1 =7^2=49, a_2=2^2 \times 5^1 = 20, a_3 = 5^1 = 5, a_4=2^1 \times 7^1 = 14$。
如果你将$a_1$替换为$1$，白板上的整数变为$1,20,5,14$，其最小公倍数为$140$。
如果你将$a_2$替换为$1$，白板上的整数变为$49,1,5,14$，其最小公倍数为$490$。
如果你将$a_3$替换为$1$，白板上的整数变为$49,20,1,14$，其最小公倍数为$980$。
如果你将$a_4$替换为$1$，白板上的整数变为$49,20,5,1$，其最小公倍数为$980$。
因此，替换后$N$个整数的最小公倍数可能为$140$、$490$或$980$，所以答案是$3$。

1
1
998244353 1000000000

1

白板上可能有很大的整数。