AtCoder Beginner Contest 276 D問題 Divide by 2 or 3
問題
提出解答
問題の概要
長さ の正の整数列
が与えられる.
次の操作を 回以上行い,
にすることは可能か? 可能ならば操作回数の最小値を求めよ.
が
の倍数であるような
以上
以下の整数
を選び,
を
に置き換える.
が
の倍数であるような
以上
以下の整数
を選び,
を
に置き換える.
制約
解法
操作は可換であるので, 各項において, をそれぞれ何回割るかに着目すれば良い.
と正の整数
において,
で
を
で割り切れる最大回数と定義する.
このとき, 正の整数 が操作によって操作
にすることが可能であることの必要十分条件は
となるような非負整数が存在することであり, 操作回数は
回である.
また, 非負整数 に対して,
となる整数
が存在することと,
であることが同値である.
よって, に対して正の整数からなる集合
を
とする. このとき, 操作によって全ての項が等しくすることが可能であることと,
であることが同値である.
よって, が空集合であれば不可能である.
が空集合ではないとする. このとき, 解答は
である.
計算量については を求めるパートがボトルネックで各
に対して
時間であるから, 全体では
時間である.
なお, 素因数分解を利用して考察を進めることにより, 時間で求めることもできる.