sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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"; } }