AT_abc259_e [ABC259E] LCM on Whiteboard

题目描述

白板上写有 $N$ 个整数 $a_1,\ldots,a_N$。
其中，每个 $a_i$ 都可以用 $m_i$ 个素数 $p_{i,1} < \ldots < p_{i,m_i}$ 和正整数 $e_{i,1},\ldots,e_{i,m_i}$ 表示为 $a_i = p_{i,1}^{e_{i,1}} \times \ldots \times p_{i,m_i}^{e_{i,m_i}}$。
你可以从这 $N$ 个整数中任选一个，将其改写为 $1$。
请你求出，将其中一个整数改写为 $1$ 后，白板上 $N$ 个整数的最小公倍数可能出现的不同取值有多少种。

输入格式

输入以如下格式从标准输入读入。

$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,2}$ $\vdots$ $m_N$ $p_{N,1}$ $e_{N,1}$ $\vdots$ $p_{N,m_N}$ $e_{N,m_N}$

输出格式

输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

1
1
998244353 1000000000

输出 #2

1

说明/提示

限制条件

• $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} < \ldots < p_{i,m_i} \leq 10^9$
• $p_{i,j}$ 是素数
• $1 \leq e_{i,j} \leq 10^9$
• 所有输入均为整数

样例解释 1

白板上的整数为 $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$。
因此，改写后最小公倍数可能的取值为 $140,490,980$，所以本输入的答案为 $3$。

样例解释 2

白板上的整数可能非常大。

由 ChatGPT 4.1 翻译