AtCoder Beginner Contest 259 E問題 LCM on Whiteboard

問題

提出解答

問題の概要

$N$ 個の整数 $a_1, \dots, a_N$ がある. これらはそれぞれ素数 $p_{i,1}, \dots, p_{i,m_i}$ と正の整数 $e_{i,1}, \dots, e_{i,m_i}$ を用いて,

$\displaystyle a_i=\prod_{j=1}^{m_i} p_{i,j}^{e_{i,j}}$

である. このとき, $i=1,2, \dots, N$ それぞれに対して以下を求めた際に得られる整数の個数を求めよ *1 .

$\operatorname{lcm}(a_1, \dots, \widehat{a_i}, \dots, a_N)=\operatorname{lcm}(a_1, \dots, a_{i-1}, a_{i+1}, \dots, a_N)$

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq m_i$
$m_1+\dots+m_N \leq 2 \times 10^5$
$2 \leq p_{i,1} \lt \dots p_{i,j} \leq 10^9$
$p_{i,j}$ は素数
$1 \leq e_{i,j} \leq 10^9$

解法1

$N=1$ のときは $1$ のみなので, 答えは $1$ である.

以降では $N \geq 2$ とする.

最小公倍数について, 次のような重要な性質がある. ただし, $\mathbb{P}$ で素数全体の集合とする.

$n$ 個の整数 $a_1, \dots, a_n$ はそれぞれ

$\displaystyle a_i=\prod_{p \in \mathbb{P}} p^{e_{i,p}}$

であるとする. このとき,

$\displaystyle \operatorname{lcm}(a_1, \dots, a_n)=\prod_{p \in \mathbb{P}} p^{\max(e_{1,p}, \dots, e_{n,p})}$

である.

正の整数 $n$ と素数 $p \in \mathbb{P}$ に対して, $\nu_p(n)$ を

$\nu\_p(n):=\max \{k \in \mathbb{N} \mid p^k | n\}$

とする. このとき,

$\displaystyle n=\prod_{p \in \mathbb{P}} p^{\nu_p(n)}$

である.

ここで, $l:=\operatorname{lcm}(a_1, \dots, a_N)$ とする. つまり, 任意の素数 $p \in \mathbb{P}$ に対して,

$\nu_p(l)=\max (\nu_p(a_1), \dots, \nu_p(a_N))$

となる.

$b_i:=\operatorname{lcm}(a_1, \dots, \widehat{a_i}, \dots, a_N)$ としたとき, 素数 $p$ に対して, 最小公倍数の性質から, $\nu_p(b_i) \leq \nu_p(l)$ であるが, 実は $\nu_p(b_i) \lt \nu_p(l)$ ならば, $\nu_p(b_i) \geq 1$ である. つまり, $p=p_{i,j}$ となる整数 $j~(1 \leq j \leq m_i)$ が存在する. 実際,

$\nu_p(b_i)=\max (\nu_p(a_1),\dots, \widehat{\nu_p(a_i)}, \dots, \nu_p(a_N)), \quad \nu_p(l)=\max (\nu_p(a_1), \dots, \nu_p(a_N))$

であるが, $\nu_p(b_i) \lt \nu_p(l)$ であるためには, $\nu_p(l)=\nu_p(a_i)$ でなくてはならず, $\nu_p(b_i) \geq 0$ なので, $\nu_p(a_i) \geq 1$ が成り立つ.

よって, 対偶を取って, $p$ が $p_{i,1}, \dots, p_{i,m_i}$ とのどれとも一致していなければ $\nu_p(b_i)=\nu_p(l)$ なので, 後は $p=p_{i,j}$ の場合に $\nu_p(a_i)$ がどうなるかを調べれば良い.

$j=1,2, \dots, m_i$ に対して, $\nu_{p_{i,j}}(a_i) \neq \max (\nu_p(a_1), \dots, \nu_p(a_N))$ ならば, $\nu_{p_{i,j}}(b_i)=\nu_{p_{i,j}}(l)$ である. 一方で, $\nu_{p_{i,j}}(a_i)=\max (\nu_p(a_1), \dots, \nu_p(a_N))$ ならば,

$\nu_{p_{i,j}}(b_i)=\max (\nu_{p_{i,j}}(a_1),\dots, \widehat{\nu_{p_{i,j}}(a_i)}, \dots, \nu_{p_{i,j}}(a_N))$

であるが, これは $\nu_{p_{i,j}}(a_i)=\max (\nu_{p_{i,j}}(a_1), \dots, \nu_{p_{i,j}}(a_N))$ であるから, $\nu_{p_{i,j}}(b_i)$ は $\nu_{p_{i,j}}(a_1), \dots, \nu_{p_{i,j}}(a_N)$ のうちの2番目に大きな整数を意味する.

解法2

従って, 各素数 $p \in \mathbb{P}$ に対して, $\nu_p(a_1), \dots, \nu_p(a_N)$ のうち, 最大値と2番目に大きい整数をそれぞれ $\alpha_p, \beta_p$ とすると, $i=1,2, \dots, N$ に対して, $\nu_p(a_i)=\alpha_p$ ならば, $\nu_p(b_i)=\beta_p$ . そうでないならば, $\nu_p(b_i)=\alpha_p$ である.