Integer Kth Root
(math/number-theory/kth_root.hpp)

• View this file on GitHub
• Last update: 2024-01-08 19:16:08+09:00
• Include: #include "math/number-theory/kth_root.hpp"

Verified with

• test/yosupo/kth_root_integer.test.cpp

Code

#pragma once
#include <cassert>
#include <cmath>

/**
 * @brief Integer Kth Root
 */
unsigned long long kth_root(unsigned long long x, int k) {
    using ull = unsigned long long;
    assert(k >= 1);
    if (x <= 1 || k == 1) return x;
    auto check = [&](ull a) {
        ull y = x;
        int e = k;
        while (e) {
            if (e & 1) {
                if (a == 0) return false;
                y /= a;
            }
            if (a > 0 && a > y / a)
                a = 0;
            else
                a *= a;
            e >>= 1;
        }
        return y > 0;
    };
    ull res = std::pow(x, std::nextafter(1.0 / k, 0.0));
    while (check(res + 1)) ++res;
    return res;
}

#line 2 "math/number-theory/kth_root.hpp"
#include <cassert>
#include <cmath>

/**
 * @brief Integer Kth Root
 */
unsigned long long kth_root(unsigned long long x, int k) {
    using ull = unsigned long long;
    assert(k >= 1);
    if (x <= 1 || k == 1) return x;
    auto check = [&](ull a) {
        ull y = x;
        int e = k;
        while (e) {
            if (e & 1) {
                if (a == 0) return false;
                y /= a;
            }
            if (a > 0 && a > y / a)
                a = 0;
            else
                a *= a;
            e >>= 1;
        }
        return y > 0;
    };
    ull res = std::pow(x, std::nextafter(1.0 / k, 0.0));
    while (check(res + 1)) ++res;
    return res;
}

Back to top page