きままにものづくり

日々の気付いたことなんかを書いてます。

SRM599Div1Easy

問題

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

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

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

解法

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

計算量

O(N) or O(log V)
N:要素数
V:要素の最大値

コード