高精度整数开 m 次根

版权信息： [HNOI2004] 高精度开根

任务总览

题目描述

晓华所在的工作组正在编写一套高精度科学计算的软件，一些简单的部分如高精度加减法、乘除法早已写完了，现在就剩下晓华所负责的部分：​实数的高精度开 mm 次根​。

因为一个有理数开根之后可能得到一个无理数，所以这项工作是有较大难度的。

为了简化问题，我们 ​只对自然数进行整数次根计算​，并 截断取整 作为最终结果。

程序需要根据输入的开根次数 mm 和被开根的整数 nn，计算并输出其非负根取整后的值。

输入格式

• 第一行： 一个正整数 mm (1 ≤ mm ≤ 50)，表示开根的次数。
• 第二行： 一个整数 nn (0 ≤ nn ≤ 101000010^{10000})，表示被开根的数。

输出格式

• ​输出一行​，即为 ​nn 的 mm 次根取整后的结果​。

样例输入 1

3
1000000000

样例输出 1

1000

提示

1. 高精度处理
   • 由于 nn 长度可能高达 10,000 位，​普通数据类型无法直接存储​，需要 ​使用字符串存储并进行高精度计算​。
   • Python 的 int 类型支持大整数，可以直接进行高精度计算，而 C++ 需要使用 BigInteger 或手写高精度运算。
2. 数值范围分析
   • 若 m=50m = 50，且 nn 为最大值 101000010^{10000}，则 ​结果的位数大约是 10000/50=20010000 / 50 = 200 位​，仍然较大。
3. 计算方法
   • ​二分法​：
     • 在 00 到 nn 之间进行 ​二分查找​，寻找最大的 xx 使得 xm≤nx^m \leq n。
   • ​快速幂+高精度计算​：
     • 由于 mm 可能较大，计算 xmx^m 需要使用 快速幂 方法提高效率。

时间复杂度分析

总结

• ​采用二分法求解​，确保计算过程高效。
• ​高精度存储与计算​，避免溢出问题。
• ​保证输出截断取整​，而非四舍五入。