毎回半分なら計算量はO(log(N))ですが、毎回sqrtなら計算量はO(log log(N))

• とある問題 https://codeforces.com/contest/1469/problem/D
• のeditorialにて、問題のサイズが処理1回ごとにsqrtされる解法があった https://codeforces.com/blog/entry/86082
• その場合のステップ数はO(log log N)になる

より理解したい人へ

• What would cause an algorithm to have O(log log n) complexity?
  • https://stackoverflow.com/questions/16472012/what-would-cause-an-algorithm-to-have-olog-log-n-complexity
  • たとえば2¹⁰⁰を考えて、毎回半分だと2の肩は1ずつしか減らないが、sqrtだと2の肩が毎回半分になる