問題概要
$H \times W \ $枚のピースのからなる一枚のチョコレートがあり、全てのピースは同じ大きさの正方形である。
チョコレートをピースの継ぎ目に沿って一直線に切ることしかできないとき、$N \ $ピースからなる一枚のチョコレートを切り出すのに必要な切る回数の最小値を求めよ。
制約
- $1 \leq H, W \leq 10^6$
- $1 \leq N \leq 10^{12}$
小課題
- $1 \leq H,W \leq 10^3$
- $1 \leq N \leq 10^6$
解説
小課題
切り出すチョコレートの縦と横の長さを全探索することで、$O(HW) \ $で解を求めることができます。
満点解法
少し考えれば$ \ 3 \ $回以上切る必要はないことがわかります。
よって、$0 \ $回$ \ 1 \ $回$ \ 2 \ $回の場合について考えればいいです。
$H \times W = N \ $の場合は当然$ \ 0 \ $回です。
$H \times k = N, (1 \leq k \leq W) \ $または$ \ W \times k = N, (1 \leq k \leq H) \ $となる整数$ \ k \ $が存在すれば$ \ 1 \ $回です。
$i \times j = N, (1 \leq i \leq H),(1 \leq j \leq W) \ $を満たす$ \ i,j \ $が存在するならば$ \ 2 \ $回です。 このような$ \ i,j \ $の組は$ \ N \ $の約数を調べるか、$i, j \ $をそれぞれ全探索すればよいです。
これら全てを満たさないような場合は$ \ -1 \ $を出力すればよいです。
計算量は$ \ 2 \ $回の場合を調べるのに、$N \ $の約数を調べるならば$ \ O(\sqrt{N}) \ $、$i,j \ $それぞれを全探索するならば$ \ O(H + W) \ $となります。
