test/yosupo/kth_root_integer.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 19:16:08+09:00
• Problem: https://judge.yosupo.jp/problem/kth_root_integer

Depends on

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

Code

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

#include "../../math/number-theory/kth_root.hpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        unsigned long long A;
        int K;
        cin >> A >> K;
        cout << kth_root(A, K) << "\n";
    }
}

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

#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;
}
#line 4 "test/yosupo/kth_root_integer.test.cpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        unsigned long long A;
        int K;
        cin >> A >> K;
        cout << kth_root(A, K) << "\n";
    }
}

Back to top page