問題
現在の値をXとした時、以下の2つの操作が可能である。
AとBの2つの数字が与えられる。 を計算するのに必要な最小のステップを求めよ。
解法
Aを素因数分解する。素因数の数と、素因数の出現回数の最大値にBをかけた値のlogを足しあわせたものが答えとなる。全ての素因数をXに含めるために素因数の数だけ素数をかける必要がある。すべての素因数が揃えば、どの素因数の組み合わせも約数になるので出現回数の最大値にBをかけてlogをとった回数の操作でBにすることができる。
計算量
N:要素数
V:要素の最大値