Codeforces Round #696 (Div. 2) B. Different Divisors

問題概要

正の整数$d$が与えられる
以下の条件を満たす正の整数$a$の中で最小のもとを求めよ

• 約数を少なくとも4つ持つ
• 約数を昇順に並べたときに隣り合った約数の差が少なくとも$d$

解法

約数を4つ持つということは
$p, q$を素数とすると、

$a = p^3$ (1)
または
$a = pq$ (2)
という形に素因数分解されるとわかる

仮に、4つよりも大きい約数を持つ数が解になった場合を考える
例えば、$a = p^4$という数を考えると、
この数は$1, p, p^2, p^3, p^4$を約数にもち、
隣りあう2数の差が全て$d$以上とわかる
このとき、$a = p^3$という数を考えると、この数の約数の集合は先ほどあげた約数の部分集合になっており、
隣りあう2数の差が全て$d$以上でかつより小さい数になる
他のケースでも同様のことがいえて4つよりも大きい約数を持つ数を考える必要はない

(1)の場合は
約数を昇順に並べると$\{1, p, p^2, p^3\}$となり、
$p \le d+1$を満たす最小の素数をとってこれば良い

(2)の場合は
約数を昇順に並べると$\{1, p, q, pq\} (p < q)$となり、
$p \le d+1, q \le p+d$を満たす素数のペアをとってこれば良い

$p^2 \ge q$となるかどうかで(1)になるか(2)になるかが決まるが、
制約がそこまで大きな数でないので、(1)の方がよいということは考えられず(素数にそこまで間隔が開くことがない)
実際には(2)だけ調べれば良い

提出コード

https://codeforces.com/contest/1474/submission/105289639