整数の平方根
(src/math/sqrt.hpp)

• View this file on GitHub
• Last update: 2026-10-12 19:23:31+09:00
• Include: #include "src/math/sqrt.hpp"

関数	説明	計算量
sqrtll(n)	$\lfloor \sqrt{n} \rfloor$ ($0 \le n < 2^{63}$)。浮動小数点の誤差なしで求める	$O(\log n)$

long long r = sqrtll(1000000000000000000LL);  // 1000000000
long long s = sqrtll(15);                      // 3

Verified with

• test/yosupo/enumerate-quotients.test.cpp

Code

#pragma once

/**
 * @file sqrt.hpp
 * @brief 整数の平方根
 */

/**
 * @brief floor(sqrt(n))
 * @param n 平方根を求めたい整数 long long 型で 0 <= n < 2^63 を満たす
 * @return long long
 */
inline long long sqrtll(long long n) { 
    // 3037000500 = ceil(sqrt(2^63))
    long long le = 0, ri = 3037000500; 
    while(ri - le > 1) {
        long long mid = (le + ri) / 2;
        if(mid * mid <= n) le = mid;
        else ri = mid;
    }
    return le;
}

#line 2 "src/math/sqrt.hpp"

/**
 * @file sqrt.hpp
 * @brief 整数の平方根
 */

/**
 * @brief floor(sqrt(n))
 * @param n 平方根を求めたい整数 long long 型で 0 <= n < 2^63 を満たす
 * @return long long
 */
inline long long sqrtll(long long n) { 
    // 3037000500 = ceil(sqrt(2^63))
    long long le = 0, ri = 3037000500; 
    while(ri - le > 1) {
        long long mid = (le + ri) / 2;
        if(mid * mid <= n) le = mid;
        else ri = mid;
    }
    return le;
}

Back to top page