第四题 - A23469.奇怪的次方 题目链接跳转：A23469.奇怪的次方 根据题目要求，我们需要找到一个整数 XXX，满足 XN=YX^N = YXN=Y。根据数学的基本运算法则，我们对等式两遍同时开 NNN 次根即可得到 X=YNX = \sqrt[N]{Y}X=NY 。最后判断再校验一边答案即可。需要注意的是，本题涉及关于小数的运算，因此在实现过程中需要使用 double 数据类型，同时也要关注计算机在处理浮点数存在的误差（使用 round 函数可以将一个数字四舍五入）。 本题的 AC 代码如下： 本题的 Python 代码如下： 本算法的时间复杂度约为 O(1)O(1)O(1) 级别。对于 pow 函数的时间复杂度无法被精确地推算，因为在 C++ 底层中该函数会使用多种不同的算法来实现相同的功能，但一般情况是 log2(n)log_2(n)log2 (n) 级别的。

题目解析 显然 XXX 越大， XNX^NXN 就越大，答案有单调性，所以我们可以使用二分来快速计算 XXX 的值。 AC代码 C++ AC代码： Python AC代码： 复杂度分析 对于每个 Testcase\tt{Testcase}Testcase 使用二分来确定 XXX 的值，每次验证答案的复杂度为 O(N)\mathrm{O}(N)O(N)，总的时间复杂度为 O(log⁡NY)\mathrm{O}(\log{NY})O(logNY)。

首先，我们得了解几个知识： (n×m)k=nk×mk(n×m)^k=n^k×m^k(n×m)k=nk×mk nk1k2=(nk1)k2n^{k1k2}=(n^{k1})^{k2}nk1k2=(nk1)k2 我们分解质因数，如果Y=XNY=X^NY=XN，那么Y的每一个质因子的次数都应是NNN的倍数 如果有任何一个不是，那么Y≠XNY\not=X^NY=XN. 那么如果是的话，该怎么算呢？ 简单，我们把每一个质因子次数除以N乘起来就是X了！ 单个测试数据时间复杂度：O(n)O(\sqrt n)O(n ) 好了，你已经会这道题了，请做一下这道吧（

我们将 Xn=YX^n=YXn=Y 这个式子两边同时开 nnn 次方得： X=YnX=\sqrt[n]{Y}X=nY 也就是说 XXX 存在的条件是 Yn\sqrt[n]{Y}nY 为整数。 这个式子无法直接计算，但是变形得： Yn=Y1n\sqrt[n]{Y}=Y^{\frac{1}{n}}nY =Yn1 右式可以使用 <cmath> 中的 std::pow() 函数直接计算。 小提示：浮点题精度一定要高，可以用 long double，反正不卡时间。

很显然，x越大，得到的结果也越大。因此，这里具有单调性，能用二分。