test/kthrooti.test.cpp

• View this file on GitHub
• Last update: 2024-03-03 06:51:22+09:00
• Problem: https://judge.yosupo.jp/problem/kth_root_integer

Depends on

• k乗根(整数) (C++/math/kthrooti.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/kth_root_integer"
#include <iostream>
#include "C++/math/kthrooti.hpp"
void solve() {
    ul a;
    int k;
    std::cin >> a >> k;
    std::cout << Heileden::kthrooti(a, k) << '\n';
}
int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    int t;
    std::cin >> t;
    while(t--) {
        solve();
    }
}

#line 1 "test/kthrooti.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/kth_root_integer"
#include <iostream>
#line 2 "C++/math/kthrooti.hpp"

#include <limits>
#ifndef TEMPLATE
typedef unsigned long long ul;
template <class T, class U> inline bool overflow_if_mul(const T a, const U b){ return (std::numeric_limits<T>::max()/a)<b; }
#endif
namespace Heileden {
inline ul kthrooti(const ul n, const int k) {
    if(k==1) {
		return n;
	}
	const auto chk=[&](const unsigned x) {
		ul mul=1;
		for(int i = 0; i < k; ++i) {
            if(overflow_if_mul(mul, x)) {
                return false;
            }
            mul*=x;
        }
		return mul<=n;
	};
	ul ret=0;
	for(int i = 32; --i >= 0;) {
		if(chk(ret|(1U<<i))) {
			ret|=1U<<i;
		}
	}
	return ret;
}
}

/**
 * @brief k乗根(整数)
 */
#line 4 "test/kthrooti.test.cpp"
void solve() {
    ul a;
    int k;
    std::cin >> a >> k;
    std::cout << Heileden::kthrooti(a, k) << '\n';
}
int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    int t;
    std::cin >> t;
    while(t--) {
        solve();
    }
}

Back to top page