utilities/test/kth_root_integer.test.cpp

View this file on GitHub
Last update: 2021-05-01 20:55:29+09:00
Problem: https://judge.yosupo.jp/problem/kth_root_integer

Depends on

utilities/int_kth_root.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/kth_root_integer"
#include "../int_kth_root.hpp"
#include <iostream>
using namespace std;

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

    int T;
    cin >> T;
    while (T--) {
        unsigned long long a;
        int k;
        cin >> a >> k;
        cout << int_kth_root(a, k) << '\n';
    }
}

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

// CUT begin
// floor(a^(1/k)) (the largest x s.t. x^k doesn't exceed a)
// Constraints: a >= 0, k > 0
unsigned long long int_kth_root(unsigned long long a, int k) {
    using Int = __int128;
    if (a == 0) {
        return 0;
    } else if (k == 1) {
        return a;
    } else {
        Int ok = 1, ng = Int(a) + 1;
        while (ng - ok > 1) {
            Int c = (ok + ng) / 2, p = c;
            for (int t = 0; t < k - 1; t++) {
                p *= c;
                if (p > a) break;
            }
            (p > a ? ng : ok) = c;
        }
        return ok;
    }
}
#line 3 "utilities/test/kth_root_integer.test.cpp"
#include <iostream>
using namespace std;

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

    int T;
    cin >> T;
    while (T--) {
        unsigned long long a;
        int k;
        cin >> a >> k;
        cout << int_kth_root(a, k) << '\n';
    }
}