lib/math/kth_root_integer.hpp

View this file on GitHub
Last update: 2024-04-29 04:13:12+09:00
Include: #include "lib/math/kth_root_integer.hpp"

Verified with

test/library_checker/number_theory/kth_root_integer.test.cpp

Code

#pragma once

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 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;
}