AtCoder Regular Contest 150 B問題 Make Divisible
問題
提出解答
問題の概要
が
の倍数であるという条件下における
の最小値を求めよ.
ケースのマルチケース
制約
解法
を固定する. このとき,
が
の倍数になるような最小の非負整数
を
と書くことにする.
のとき
このとき, であるから,
が
の倍数であるとき,
を最小にするためには
であるから,
でなくてはならない. よって,
である. よって,
である.
は非負整数を任意にとすることができるので,
とすると
を最小にすることができ, このとき,
である.
のとき
一般に, 整数 を正の整数
で割った余りが
であるとき,
が成り立つ.
よって, 各 に対して, 余りに着目することで,
が
の倍数であるような最小の非負整数
は
である.
が
の倍数の場合
この場合, である. そして,
は
の約数である.
であるから, このような
が
の約数になるような最小の非負整数
を取るべきである. これは
の
以上の最小の約数を
としたとき,
である.
が
の倍数ではない場合.
この場合,
である.
であるような
をまとめて考える. このとき,
であるから, として,
を満たすような 最小の非負整数を取るべきである.
また, を満たすような
の範囲は2つの整数
*1 に対して,
となる. よって,
である. よって,
のとき, 非負整数
が存在して, 最小値は
である.
このような の候補の数を考えると, 商列挙の考えから,
個である.
よって, 1テストケース当たり約数の探索と商列挙がボトルネックになり, 時間で求めることができた.
*1: の可能性もある