test/yosupo/math/kth_root_integer.test.cpp

• View this file on GitHub
• Last update: 2026-03-24 01:55:57+09:00
• Problem: https://judge.yosupo.jp/problem/kth_root_integer

Depends on

• めぐる式二分探索 (lib/algorithm/binary_search.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/kth_root_integer
#include <cmath>
#include <iostream>
#include "algorithm/binary_search.hpp"

int main(void) {
    int q;
    std::cin >> q;
    while (q--) {
        std::uint64_t a, k;
        std::cin >> a >> k;
        if (a == 0 || a == 1 || k == 1) {
            std::cout << a << '\n';
            continue;
        }
        if (k == 64) {
            std::cout << 1 << '\n';
            continue;
        }
        if (k >= 41) {
            if (a >= (1ul << k)) std::cout << 2 << '\n';
            else std::cout << 1 << '\n';
            continue;
        }
        if (k == 2) {
            std::cout << (std::uint64_t)sqrtl(a) << '\n';
            continue;
        }
        auto f = [&](std::uint64_t x) {
            __uint128_t q = 1;
            for (int i = 0; i < k; ++i) {
                q *= x;
                if (q > a) break;
            }
            return q <= a;
        };
        std::cout << meguru_binary_search(1, 2642246, f) << '\n';
    }

    return 0;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: algorithm/binary_search.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_k2_00	AC	974 ms	4 MB
g++	all_k2_01	AC	967 ms	4 MB
g++	all_k3_00	AC	984 ms	3 MB
g++	all_k3_01	AC	991 ms	4 MB
g++	all_k3_2_00	AC	1113 ms	4 MB
g++	all_k3_2_01	AC	1075 ms	4 MB
g++	example_00	AC	3 ms	4 MB
g++	near_border_00	AC	804 ms	3 MB
g++	near_border_01	AC	799 ms	3 MB
g++	near_border_02	AC	800 ms	3 MB
g++	near_border_2_00	AC	953 ms	4 MB
g++	near_border_2_01	AC	939 ms	4 MB
g++	near_border_2_02	AC	954 ms	3 MB
g++	random_00	AC	865 ms	3 MB
g++	random_01	AC	1028 ms	3 MB

Back to top page