test/library_checker/number_theory/kth_root_integer.test.cpp

View this file on GitHub
Last update: 2024-11-04 03:12:13+09:00
Problem: https://judge.yosupo.jp/problem/kth_root_integer

Depends on

lib/math/kth_root_integer.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/kth_root_integer"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/math/kth_root_integer.hpp"

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

#line 1 "test/library_checker/number_theory/kth_root_integer.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/kth_root_integer"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/math/kth_root_integer.hpp"

unsigned long long kthRoot(unsigned long long a, unsigned long long k){
    unsigned long long tmp = powl(a, (long double) 1 / (long double) k);
    unsigned long long res = 0;
    vector<unsigned long long> border = {tmp - 1, tmp, tmp + 1};
    for(auto x : border){
        if(x == 0) continue;
        unsigned long long curr = a;
        for(int i = 0; i < (int) k; i++){
            curr /= x;
        }
        if(curr >= 1) res = max(res, x);
    }
    return res;
}
#line 6 "test/library_checker/number_theory/kth_root_integer.test.cpp"

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