Kth Root(Integer)
(Math/kthroot.hpp)

• View this file on GitHub
• Last update: 2022-12-27 02:24:35+09:00
• Include: #include "Math/kthroot.hpp"

Required by

• Count Square-free integers (Math/countsquarefree.hpp)

Verified with

• Verify/LC_kth_root_integer.test.cpp

Code

#pragma once

uint64_t Kthroot(uint64_t k, uint64_t a) {
    assert(k >= 1);
    if (a == 0 || a == 1 || k == 1) return a;
    if (k >= 64) return 1;
    if (k == 2) return sqrtl(a);
    if (a == uint64_t(-1)) --a;
    struct S {
        uint64_t v;
        S& operator*=(const S& o) {
            v = v <= uint64_t(-1) / o.v ? v * o.v : uint64_t(-1);
            return *this;
        }
    };
    auto power = [&](S x, ll n) -> S {
        S v{1};
        while (n) {
            if (n & 1) v *= x;
            x *= x;
            n /= 2;
        }
        return v;
    };
    uint64_t res = pow(a, nextafter(1 / double(k), 0));
    while (power(S{res + 1}, k).v <= a) ++res;
    return res;
}

/**
 * @brief Kth Root(Integer)
*/

#line 2 "Math/kthroot.hpp"

uint64_t Kthroot(uint64_t k, uint64_t a) {
    assert(k >= 1);
    if (a == 0 || a == 1 || k == 1) return a;
    if (k >= 64) return 1;
    if (k == 2) return sqrtl(a);
    if (a == uint64_t(-1)) --a;
    struct S {
        uint64_t v;
        S& operator*=(const S& o) {
            v = v <= uint64_t(-1) / o.v ? v * o.v : uint64_t(-1);
            return *this;
        }
    };
    auto power = [&](S x, ll n) -> S {
        S v{1};
        while (n) {
            if (n & 1) v *= x;
            x *= x;
            n /= 2;
        }
        return v;
    };
    uint64_t res = pow(a, nextafter(1 / double(k), 0));
    while (power(S{res + 1}, k).v <= a) ++res;
    return res;
}

/**
 * @brief Kth Root(Integer)
*/

Back to top page