AtCoder Beginner Contest 280 D問題 Factorial and Multiple
問題
提出解答
問題の概要
が
の倍数であるような最小の正の整数
を求めよ.
制約
解法
正の整数 と素数
に対して,
で
を割り切る
の最大回数とする.
このとき, 整数 と素数
に対して,
が成り立つことから,
が成り立つ.
そして, 右辺について, 正の整数 に対して,
が成り立つことから,
となる *1.
ここで, であることと,
が
の倍数であることは同値である.
以上
以下の整数のうち,
の倍数であるような整数は
個である. よって,
である.
また, 正の整数 に対して,
が
の倍数であることの必要十分条件は, 任意の素数
に対して,
が成り立つことである.
そして, は
について単調増加である.
以上から, の素因数分解を
とすると,
が
の倍数であることと, 以下の条件
は同値である.
任意の
に対して,
不等式において右辺は に依らない定数, 右辺は
に関して単調増加である. よって, 全体の条件も
に関して単調増加である. また,
は明らかに
の倍数である. よって,
以上
以下の範囲で
を満たすような最小の整数
を二分探索で見つけることが出来る.
計算量については の素因数分解が
時間,
の素因数の個数
が
であることに注意すると, 1つの
について
を満たしているかどうかの確認は各
について
の範囲を調べればよいので,
時間である. よって,
全体では
より
時間である. よって, 二分探索で
を満たす最小の
を見つけるのに
時間かかる.
よって, 全体では 時間になる.
*1:無限和の交換を行っているように見えるが, 十分大きい については後述の理由から
以下の全ての整数で
とはなり得ない. よって, 実質的に有限和となっている.