きままにものづくり

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

POJ 2100 : Graveyard Design

問題

 1 \leq N \leq 10^{14} を満たす整数Nが与えられる。連続する数字の二乗和でNとなる数と、その内訳を答える。

解法

しゃくとり法を用いる。入力が大きいのでオーバーフローしないように注意する。long longではオーバーフローしてしまった。二乗和なので、探索範囲の最大値は\sqrt{N}となる。

計算量

 O(\sqrt{N})
N:与えられる数

コード