平方数かどうかの判定

さっさとこうすればよかったんじゃないか。

int main(){
  ULL n = 0;
  ULL oldn;
  ULL i = 0;
  while(true){
    ULL rt = ULL(sqrt(double(n)));
    if(rt * rt != n || rt != i){
      MSG(NG);
      DP(i);
      break;
    }
    i++;
    oldn = n;
    n += i * 2 - 1;
    if(oldn > n) break;
  }
  MSG(END);
}

2分半CPUをぶんまわして「平方数なのに平方数ではないと判定されるケース」がないことを確認した。一方rt * rt == nでチェックするので「平方数ではないのに平方数だと判定されるケース」もない(乗算でオーバーフローしたら別だけど今回はしないことがわかっている)

というわけでunsigned long longな整数が平方数かどうかの判定はdoubleにしてsqrtして結果を2乗したら元に戻るかどうかを見る方法で十分、という結論が出た。どうするのが最速かを考えるのはやめておく。今日はC++しすぎてかなり消耗した。