LCM on Whiteboard

题目描述

白板上写着 $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}$。
你将从这 $N$ 个整数中选择一个并把它替换为 $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,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

1
1
998244353 1000000000

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} \lt \ldots \lt p_{i,m_i} \leq 10^9$ $p_{i,j}$ 是素数。 $1 \leq e_{i,j} \leq 10^9$ 输入中的所有数值均为整数。白板上的整数是 $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$。
白板上的整数可能非常大。

标签: AtCoder|abc259E

来源

AtCoder|abc259E