GCJ 2013 Round1A A.Bullseye

問題

白黒の円を交互に描きたい。
同心円で、半径rの白い円の外に半径1の黒い丸を描き、その外に半径1の白い丸、その外側に半径1の黒い丸、のように描いていく。
白い円は今回描く必要はなく、黒い丸を描いていきたい。
今、tミリリットルの墨があり、1ミリリットルでπcm^2の面積を塗りつぶせる。
与えられた墨で、完全な丸を描いていくとき、黒い丸は最大何個描けるか？

1<=r<=10^18
1<=t<=2*10^18

考え方

2分探索。

i個目の黒い丸を描いた時の墨の量は、「黒い円の面積-白い円の面積」で求められるので、
(r+2i-1)^2 - (r+2i-2)^2 = 2r + 4i - 3
1からi個までの黒い円を描いたときの墨の合計量は、
Σ_i (2r+4i-3) = 4Σi + Σ(2r-3) = 2i(i+1) + i(2r-3) = i * (2i + 2r - 1)
なので、2分探索で「上記の総和<=t」となる最大のiを求めればよい。

ただし、rは10^18までありうるので、64bit整数では足りないので、多倍長整数を使う。
(解説記事だと、チェックを小数でやっても大丈夫ぽいことが書いてある)