/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の整数 a_1,\ldots,a_N が白板に書かれています。
ここで、a_i は m_i 個の素数 p_{i,1} \lt \ldots \lt 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 個の整数の最小公倍数としてあり得る値の個数を求めてください。
制約
- 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
白板に書かれている整数はとても大きい場合があります。
Score : 500 points
Problem Statement
There are N integers a_1,\ldots,a_N written on a whiteboard.
Here, a_i can be represented as a_i = p_{i,1}^{e_{i,1}} \times \ldots \times p_{i,m_i}^{e_{i,m_i}} using m_i prime numbers p_{i,1} \lt \ldots \lt p_{i,m_i} and positive integers e_{i,1},\ldots,e_{i,m_i}.
You will choose one of the N integers to replace it with 1.
Find the number of values that can be the least common multiple of the N integers after the replacement.
Constraints
- 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} is prime.
- 1 \leq e_{i,j} \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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}
Output
Print the answer.
Sample Input 1
4 1 7 2 2 2 2 5 1 1 5 1 2 2 1 7 1
Sample Output 1
3
The integers on the whiteboard are 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.
If you replace a_1 with 1, the integers on the whiteboard become 1,20,5,14, whose least common multiple is 140.
If you replace a_2 with 1, the integers on the whiteboard become 49,1,5,14, whose least common multiple is 490.
If you replace a_3 with 1, the integers on the whiteboard become 49,20,1,14, whose least common multiple is 980.
If you replace a_4 with 1, the integers on the whiteboard become 49,20,5,1, whose least common multiple is 980.
Therefore, the least common multiple of the N integers after the replacement can be 140, 490, or 980, so the answer is 3.
Sample Input 2
1 1 998244353 1000000000
Sample Output 2
1
There may be enormous integers on the whiteboard.