官方题解｜奇怪的次方

题目解析

显然 $X$ 越大， $X^N$ 就越大，答案有单调性，所以我们可以使用二分来快速计算 $X$ 的值。

AC代码

C++ AC代码：

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

constexpr int INF = 1e9;

i64 f(i64 x, int n) {
    i64 res = 1;
    for (int i = 1; i <= n; ++i) {
        if (res >= INF) return INF;
        res *= x;
    }
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n, y;
        cin >> n >> y;
        i64 lo = 1, hi = y;
        while (lo < hi) {
            i64 mid = lo + hi >> 1;
            if (f(mid, n) < y)
                lo = mid + 1;
            else
                hi = mid;
        }
        i64 res = f(lo, n);
        cout << (res == y ? lo : -1) << '\n';
    }
    return 0;
}

Python AC代码：

for _ in range(int(input())):
    n, y = map(int, input().split())
    lo, hi = 0, y
    while lo < hi:
        mid = lo + hi >> 1
        if mid**n < y:
            lo = mid + 1
        else:
            hi = mid
    print(lo if lo**n == y else -1)

复杂度分析

对于每个 $\tt{Testcase}$ 使用二分来确定 $X$ 的值，每次验证答案的复杂度为 $\mathrm{O}(N)$，总的时间复杂度为 $\mathrm{O}(\log{NY})$。