分数: 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}.
您将选择以下之一 N 整数来替换它 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}
输出
打印答案。
示例输入 1
4 1 7 2 2 2 2 5 1 1 5 1 2 2 1 7 1
示例输出 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.
示例输入 2
1 1 998244353 1000000000
示例输出 2
1
白板上可能有巨大的整数。