cpp/math/exactsqrt.cpp

• View this file on GitHub
• Last update: 2024-01-24 16:14:34+09:00

Required by

• cpp/geometry/two-points-distance.cpp
• cpp/math/meissel-lehhmer.cpp

Verified with

• cpp/z_test/yosupo-counting_primes.cpp

Code

// 整数型を取得することを想定
template <typename T>
T CeilExactSqrt(int c, T x){
  T mn = 0;
  T mx = x;
  while(mx-mn > 1){
    T ce = (mn+mx)/2;
    T nw = 1;
    for(int i = 0; c > i; i++){
      if(x/ce < nw){
        mx = ce;
        break;
      }
      nw *= ce;
      if(i+1 == c && x == nw){
        mx = ce;
      }
    }
    if(mx != ce)mn = ce;
  }
  return mx;
}

template <typename T>
T FloorExactSqrt(int c, T x){
  T mn = 0;
  T mx = x;
  while(mx-mn > 1){
    T ce = (mn+mx)/2;
    T nw = 1;
    for(int i = 0; c > i; i++){
      if(x/ce < nw){
        mx = ce;
        break;
      }
      nw *= ce;
    }
    if(mx != ce)mn = ce;
  }
  return mn;
}

#line 1 "cpp/math/exactsqrt.cpp"
// 整数型を取得することを想定
template <typename T>
T CeilExactSqrt(int c, T x){
  T mn = 0;
  T mx = x;
  while(mx-mn > 1){
    T ce = (mn+mx)/2;
    T nw = 1;
    for(int i = 0; c > i; i++){
      if(x/ce < nw){
        mx = ce;
        break;
      }
      nw *= ce;
      if(i+1 == c && x == nw){
        mx = ce;
      }
    }
    if(mx != ce)mn = ce;
  }
  return mx;
}

template <typename T>
T FloorExactSqrt(int c, T x){
  T mn = 0;
  T mx = x;
  while(mx-mn > 1){
    T ce = (mn+mx)/2;
    T nw = 1;
    for(int i = 0; c > i; i++){
      if(x/ce < nw){
        mx = ce;
        break;
      }
      nw *= ce;
    }
    if(mx != ce)mn = ce;
  }
  return mn;
}

Back to top page