SRM635 Div2Med QuadraticLaw

問題文
本来の授業時間 d が与えられる。授業の開始を t 遅らせるとき、更に t^2 の時間だけ授業時間が少なくなる。授業時間をできるだけ少なくするための t を求めよ。

解説
入力が10^18なので普通に線形探索は不可。二分探索しても良いが、整数型で探索範囲は削れる。方法はいくつか有るようだが、一つの例として√を整数切り捨てで計算したとき t の値が √(d+1) * √(d+1) 以上にはならないことを利用すると探索範囲を大幅に削ることが出来る。そこから線形探索で t の値をデクリメントしながら整数切り捨ての計算で二乗が d と一致したときの t の値がちょうど答え。解はすぐ見つかる。

以下は本番コードの変数名を書き換えて無駄な宣言を消したコード。
数行で書ける数学系の Div2Med の問題としては簡単めだと思う。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

class QuadraticLaw {
public:
  long long getTime(long long d) {
    ll SQRTD = sqrt(d);
    ll t = sqrt(pow(SQRTD+1, 2.));
    
    for(;;) {
      if(t*t <= d-t) { return t; }
      t --;
    }
  }
};