$\mathrm{floor}(a^{\frac{1}{k}})$
(math/kth-root-integral.hpp)

• View this file on GitHub
• Last update: 2020-12-05 07:59:51+09:00
• Include: #include "math/kth-root-integral.hpp"

$\mathrm{floor}(a^{\frac{1}{k}})$

概要

整数$a$の$k$乗根(切り捨て)を求めるライブラリ。

$a,k$の値によってpowl関数が上下両方に誤差を発生しうることに注意して実装する。

使い方

• kth_root_integral(a, k)　:　$a$の$k$乗根を求める。

Verified with

• verify/verify-yosupo-math/yosupo-kth-root-integral.test.cpp

Code

#pragma once



uint64_t kth_root_integral(uint64_t a, uint64_t k) {
  if (a <= 1 || k == 1) return a;
  if (64 <= k) return 1;
  auto check = [&](__uint128_t n) {
    __uint128_t x = 1, m = n;
    for (int p = k; p; p >>= 1, m *= m)
      if (p & 1) x *= m;
    return x <= a;
  };
  uint64_t n = powl(a, (long double)(1.0) / k);
  while (!check(n)) --n;
  while (check(n + 1)) ++n;
  return n;
}

/**
 * @brief $\mathrm{floor}(a^{\frac{1}{k}})$
 * @docs docs/math/kth-root-integral.md
 */

#line 2 "math/kth-root-integral.hpp"



uint64_t kth_root_integral(uint64_t a, uint64_t k) {
  if (a <= 1 || k == 1) return a;
  if (64 <= k) return 1;
  auto check = [&](__uint128_t n) {
    __uint128_t x = 1, m = n;
    for (int p = k; p; p >>= 1, m *= m)
      if (p & 1) x *= m;
    return x <= a;
  };
  uint64_t n = powl(a, (long double)(1.0) / k);
  while (!check(n)) --n;
  while (check(n + 1)) ++n;
  return n;
}

/**
 * @brief $\mathrm{floor}(a^{\frac{1}{k}})$
 * @docs docs/math/kth-root-integral.md
 */

Back to top page