← 返回题目列表

AtCoder · abc259_e

H. 白板上的 LCM

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

分数: 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

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