math/isqrt.hpp

• View this file on GitHub
• Last update: 2023-04-10 22:57:51+09:00
• Include: #include "math/isqrt.hpp"

Required by

• 商の列挙 (math/enumerate-quotient.hpp)
• 無平方数の数え上げ (multiplicative-function/count-square-free.hpp)
• 乗法的関数のprefix sum の列挙 (multiplicative-function/enumerate-sum-of-multiplicative-function.hpp)

Verified with

• verify/verify-unit-test/enumerate-quotient.test.cpp
• verify/verify-unit-test/math.test.cpp
• verify/verify-yosupo-math/yosupo-count-squarefrees.test.cpp
• verify/verify-yosupo-math/yosupo-counting-primes-4.test.cpp
• verify/verify-yosupo-math/yosupo-enumerate-quotient.test.cpp
• verify/verify-yosupo-math/yosupo-sum-of-totient-3.test.cpp
• verify/verify-yuki/yuki-2262.test.cpp
• verify/verify-yuki/yuki-2266.test.cpp

Code

#pragma once

#include <cmath>
using namespace std;

// floor(sqrt(n)) を返す (ただし n が負の場合は 0 を返す)
long long isqrt(long long n) {
  if (n <= 0) return 0;
  long long x = sqrt(n);
  while ((x + 1) * (x + 1) <= n) x++;
  while (x * x > n) x--;
  return x;
}

#line 2 "math/isqrt.hpp"

#include <cmath>
using namespace std;

// floor(sqrt(n)) を返す (ただし n が負の場合は 0 を返す)
long long isqrt(long long n) {
  if (n <= 0) return 0;
  long long x = sqrt(n);
  while ((x + 1) * (x + 1) <= n) x++;
  while (x * x > n) x--;
  return x;
}

Back to top page