AtCoder Beginner Contest 259 E問題 LCM on Whiteboard
問題
提出解答
問題の概要
個の整数
がある. これらはそれぞれ素数
と正の整数
を用いて,
である. このとき, それぞれに対して以下を求めた際に得られる整数の個数を求めよ *1 .
制約
は素数
解法1
のときは
のみなので, 答えは
である.
以降では とする.
最小公倍数について, 次のような重要な性質がある. ただし, で素数全体の集合とする.
個の整数
はそれぞれ
正の整数 と素数
に対して,
を
とする. このとき,
である.
ここで, とする. つまり, 任意の素数
に対して,
となる.
としたとき, 素数
に対して, 最小公倍数の性質から,
であるが, 実は
ならば,
である. つまり,
となる整数
が存在する. 実際,
であるが, であるためには,
でなくてはならず,
なので,
が成り立つ.
よって, 対偶を取って, が
とのどれとも一致していなければ
なので, 後は
の場合に
がどうなるかを調べれば良い.
に対して,
ならば,
である. 一方で,
ならば,
であるが, これは であるから,
は
のうちの2番目に大きな整数を意味する.
解法2
従って, 各素数 に対して,
のうち, 最大値と2番目に大きい整数をそれぞれ
とすると,
に対して,
ならば,
. そうでないならば,
である.
ここで, となるような素数
と
の組
の個数は高々
個である. このことから, 各
に対して, 次のような列
を考える.
- ただし, 各
は
かつ,
を満たすようなっもの全てであり,
.
- ただし, 各
すると, に対して,
であるから, 求めるべき解答は数列の集合 の濃度である.
計算量は とすると,
を求めるために辞書を用いることがボトルネックになり,
である.
*1: は
から,
を除いた列という意味である