競技プログラミング用 知識集積所
ABC420G - sqrt(n^2+n+X)
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- 特になし
考え方
nの値として、例えばXが10^14の場合、n=10^14-1までありうる。
よって、nの値で全探索※をするのは間に合わない。
よって、nの値で全探索※をするのは間に合わない。
根号を外した結果はだいたいnの値の±√Xくらいになると考えると、√(n^2+n+x) = n+k として考えるのがよいとわかる。
これを解いた n=(X-k*k)/(2*k-1) が整数かで考える。
これを解いた n=(X-k*k)/(2*k-1) が整数かで考える。
この時点で、「まあ、10倍余裕を見て-10^8≦k≦10^8くらい全探索しとけばいいでしょ」でも通る。
が、以下真面目に調査が必要な探索範囲を考えてみる。
が、以下真面目に調査が必要な探索範囲を考えてみる。
(x-k*k)/(2*k-1) が整数か ⇔ 4*(x-k*k)/(2*k-1) が整数か ⇔ (4*x-1)/(2*k-1) が整数か である。
そして、(4*x-1) = -(2*a-1)*(2*b-1) の場合、k=a と k=b で同じ値が出てくるので、|2*k-1| <= √|4*x-1| の範囲だけ考えればよい。
小数の扱いは怖いので、丸めを広い方にとって、それを探索範囲とすればよい。
そして、(4*x-1) = -(2*a-1)*(2*b-1) の場合、k=a と k=b で同じ値が出てくるので、|2*k-1| <= √|4*x-1| の範囲だけ考えればよい。
小数の扱いは怖いので、丸めを広い方にとって、それを探索範囲とすればよい。
