整数の平方根 (integer/sqrt.cpp)
- category: integer
-
View this file on GitHub
- Last commit date: 2020-04-06 23:03:06+09:00
Required by
Verified with
Code
#ifndef H_int_sqrt
#define H_int_sqrt
/**
* @brief 整数の平方根
* @author えびちゃん
*/
#include <climits>
template <typename Tp>
Tp isqrt(Tp n) {
if (n <= 1) return n;
Tp lb = 1;
Tp ub = static_cast<Tp>(1) << (CHAR_BIT * (sizeof(Tp) / 2));
while (ub-lb > 1) {
Tp mid = (lb+ub) >> 1;
((mid*mid <= n)? lb: ub) = mid;
}
return lb;
}
#endif /* !defined(H_int_sqrt) */
#line 1 "integer/sqrt.cpp"
/**
* @brief 整数の平方根
* @author えびちゃん
*/
#include <climits>
template <typename Tp>
Tp isqrt(Tp n) {
if (n <= 1) return n;
Tp lb = 1;
Tp ub = static_cast<Tp>(1) << (CHAR_BIT * (sizeof(Tp) / 2));
while (ub-lb > 1) {
Tp mid = (lb+ub) >> 1;
((mid*mid <= n)? lb: ub) = mid;
}
return lb;
}