SRM599Div1Easy

問題

現在の値をXとした時、以下の2つの操作が可能である。

• 素数pをXにかける
• Xの約数dをXにかける

AとBの2つの数字が与えられる。 を計算するのに必要な最小のステップを求めよ。

解法

Aを素因数分解する。素因数の数と、素因数の出現回数の最大値にBをかけた値のlogを足しあわせたものが答えとなる。全ての素因数をXに含めるために素因数の数だけ素数をかける必要がある。すべての素因数が揃えば、どの素因数の組み合わせも約数になるので出現回数の最大値にBをかけてlogをとった回数の操作でBにすることができる。

計算量

N:要素数
V:要素の最大値

コード