整数k乗根(K-th Root Integer)
(math/kth_root_integer.cpp)

• View this file on GitHub
• Last update: 2026-03-12 14:17:55+09:00

説明

floor(a^(1/k)) を求める。 二分探索で整数解を絞る。

できること

• ull kth_root_integer(ull a, int k) floor(a^(1/k)) を返す

使い方

0 <= a < 2^64, 1 <= k を想定する。 内部では x^k <= a を __int128 で判定する。

Verified with

• test/yosupo_kth_root_integer.test.cpp

Code

bool kth_root_integer_leq(ull x, int k, ull a) {
    __uint128_t p = 1;
    for (int i = 0; i < k; ++i) {
        p *= x;
        if (p > a) return false;
    }
    return true;
}

ull kth_root_integer(ull a, int k) {
    if (k == 1 || a <= 1) return a;
    ull ng = min<ull>(a, (1ULL << 32)) + 1, ok = 0;
    while (ng - ok > 1) {
        ull mid = ok + (ng - ok) / 2;
        if (kth_root_integer_leq(mid, k, a)) ok = mid;
        else ng = mid;
    }
    return ok;
}

/**
 * @brief 整数k乗根(K-th Root Integer)
 */

#line 1 "math/kth_root_integer.cpp"
bool kth_root_integer_leq(ull x, int k, ull a) {
    __uint128_t p = 1;
    for (int i = 0; i < k; ++i) {
        p *= x;
        if (p > a) return false;
    }
    return true;
}

ull kth_root_integer(ull a, int k) {
    if (k == 1 || a <= 1) return a;
    ull ng = min<ull>(a, (1ULL << 32)) + 1, ok = 0;
    while (ng - ok > 1) {
        ull mid = ok + (ng - ok) / 2;
        if (kth_root_integer_leq(mid, k, a)) ok = mid;
        else ng = mid;
    }
    return ok;
}

/**
 * @brief 整数k乗根(K-th Root Integer)
 */

Back to top page