Kth Root Integer (math/number-theory/kth-root-integer.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "math/number-theory/kth-root-integer.hpp"

kth_root_integer

uint64_t kth_root_integer(uint64_t a, int k)

$\textrm{floor}{(a^{\frac {1} {k}})}$ を返します。

制約

• $0 \leq a \lt 2^{64}$
• $1 \leq k \leq 64$

計算量

• $O(k \log \log a)$

Required by

• Prime Count(素数の個数) (math/number-theory/prime-count.hpp)

Verified with

• test/verify/yosupo-counting-primes.test.cpp
• test/verify/yosupo-kth-root-integer.test.cpp

Code

uint64_t kth_root_integer(uint64_t a, int k) {
  if (k == 1) return a;
  auto check = [&](uint32_t x) {
    uint64_t mul = 1;
    for (int j = 0; j < k; j++) {
      if (__builtin_mul_overflow(mul, x, &mul)) return false;
    }
    return mul <= a;
  };
  uint64_t ret = 0;
  for (int i = 31; i >= 0; i--) {
    if (check(ret | (1u << i))) ret |= 1u << i;
  }
  return ret;
}

#line 1 "math/number-theory/kth-root-integer.hpp"
uint64_t kth_root_integer(uint64_t a, int k) {
  if (k == 1) return a;
  auto check = [&](uint32_t x) {
    uint64_t mul = 1;
    for (int j = 0; j < k; j++) {
      if (__builtin_mul_overflow(mul, x, &mul)) return false;
    }
    return mul <= a;
  };
  uint64_t ret = 0;
  for (int i = 31; i >= 0; i--) {
    if (check(ret | (1u << i))) ret |= 1u << i;
  }
  return ret;
}

Back to top page