test/src/number/kth_root_round/kth_root_integer.test.cpp

• View this file on GitHub
• Last update: 2022-10-31 01:25:41+09:00
• Problem: https://judge.yosupo.jp/problem/kth_root_integer

Depends on

• $\lfloor a ^ {\frac{1}{k}}\rfloor, \lceil a ^ {\frac{1}{k}}\rceil$ (library/number/kth_root_round.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/kth_root_integer"

#include <iostream>

#include "library/number/kth_root_round.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t --> 0) {
        uint64_t a;
        int k;
        std::cin >> a >> k;
        std::cout << suisen::floor_kth_root(a, k) << '\n';
    }
    return 0;
}

#line 1 "test/src/number/kth_root_round/kth_root_integer.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/kth_root_integer"

#include <iostream>

#line 1 "library/number/kth_root_round.hpp"



#include <cmath>
#include <type_traits>

namespace suisen {
    template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
    T floor_kth_root(T x, int k) {
        if (k == 1 or x == 0 or x == 1) return x;
        if (k == 2) return ::sqrtl(x);
        if (k >= 64) return 1;
        T res = ::powl(x, ::nextafterl(1 / (long double) k, 0));
        while (::powl(res + 1, k) <= x) ++res;
        return res;
    }
    template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
    T ceil_kth_root(T x, int k) {
        T res = floor_kth_root(x, k);
        res += ::powl(res, k) < x;
        return res;
    }
} // namespace suisen



#line 6 "test/src/number/kth_root_round/kth_root_integer.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t --> 0) {
        uint64_t a;
        int k;
        std::cin >> a >> k;
        std::cout << suisen::floor_kth_root(a, k) << '\n';
    }
    return 0;
}

Back to top page