読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 057 C - 2乗根

こっちのほうが B っぽくない?(C++ でどうやるのか知らないけど)

解法

L <= sqrt(X) < L+1
とすると,
L^2 <= X < (L+1)^2

となります。これが最小かどうかは分からないので,
(L/10)^2 <= X < ((L+1)/10)^2

というように続いていきます。上の表記は実数で考えていますが, これを整数だけで表現する場合は,

  • L^2 の L を 10 で割るのは, L^2 を 100 で割って切り上げる((L^2+99)/100 を計算する)
  • (L+1)^2 の L+1 を 10 で割るのは, (L+1)^2 を 100 で割って切り捨てる((L+1)^2/100 を計算する)

とすれば良いです。式を満たす X が整数として存在している限り上記を繰り返せば良いです。

L = input()
R = (L+1)*(L+1)-1
L = L*L
while (L+99)/100 <= R/100:
    L = (L+99)/100
    R = R/100

print L