きままにものづくり

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

SRM652Div1Easy

問題

2人で行う順列ゲームを考える。Aliceはxをはじめに選び、BobはサイズNの順列を選ぶ。
AliceはBobの選んだ順列を用いてf(x)を計算する。f(x)はf(1) = p[1]、f(m) = p[f(m-1)]で計算される。
Bobがどんな順列を選んできてもf(x)=1となる最小のxを求めよ。

解法

Bobは、 1 \leq f(x) \leq Nとなる順列を選ぶことができる。よって、Bobがどんな順列を選んできてもf(x)=1となるxは、1~Nの最小公倍数と等しくなる。そのまま、計算すると大きい値になってしまうので因数の数を保持することで最小公倍数を求める。

計算量

 O(N \sqrt{N})

コード

広告を非表示にする