奇怪的次方｜数学开根法

第四题 - A23469.奇怪的次方

题目链接跳转：A23469.奇怪的次方

根据题目要求，我们需要找到一个整数 $X$，满足 $X^N = Y$。根据数学的基本运算法则，我们对等式两遍同时开 $N$ 次根即可得到 $X = \sqrt[N]{Y}$。最后判断再校验一边答案即可。需要注意的是，本题涉及关于小数的运算，因此在实现过程中需要使用 double 数据类型，同时也要关注计算机在处理浮点数存在的误差（使用 round 函数可以将一个数字四舍五入）。

本题的 AC 代码如下：

#include <iostream>
#include <cmath>
using namespace std;

int T;
double n, y;

int main(){
    cin >> T;
    while(T--){
        cin >> n >> y;
        // 计算答案。
        double root = pow(y, 1/n);
        // 校验答案是否是一个整数。
        if (pow(round(root), n) == y) 
            cout << round(root) << endl;
        else cout << -1 << endl;
    }
    return 0;
}

本题的 Python 代码如下：

T = int(input())

while T:
	T -= 1
	n, y = map(float, input().split())
	ans: float = pow(y, 1 / n)
	print(round(ans) if pow(round(ans), n) == y else -1)

本算法的时间复杂度约为 $O(1)$ 级别。对于 pow 函数的时间复杂度无法被精确地推算，因为在 C++ 底层中该函数会使用多种不同的算法来实现相同的功能，但一般情况是 $log_2(n)$ 级别的。