きままにものづくり

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

SRM617Div1Easy

問題

長さN( N \leq 100,000)のケーキが与えられる。Nの割れる数の人数が来ることは分かるが、正確な人数は分からない。来る人数に対して平等にケーキを分配するためにはいくつのピースに分けてケーキを切ればいいか求めよ。

解法

割れる数の倍数の集合を求めると、その集合のサイズが答えとなる。ある割れる数の倍数の個数は、ピースの数に対応する。例えば、N=6の時で割れる数を2とすると、必要なピースの数は3となる。これを他の数でも調べることで、全てのパターンに対応するために必要な数が求まる。
割れる数の倍数の集合の要素とNでユークリッドの互除法をとると、互いに素ではないので1以外の数字が返ってくる。これを利用することで答えを求めることができる。

計算量

全体:O(N log N)
GCD:O(log N):

コード