c++ - p 的正 n 次方根

Question

以下代码在 20 个测试用例中的一个上打印了错误答案。如果有人能找到逻辑错误，我将不胜感激。

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

int main() {
    double n, p;
    cin >> n >> p;
    int k = pow(p, 1 / n);
    cout << k;
    return 0;
}

Answer 1

问题表明 p ≤ 10^100。对于该大小 (*) 的所有整数，没有精确的 double 表示。如果p最接近的浮点表示小于精确的p，则pow(p, 1/n);返回的浮点值code> 也将小于预期的 k。

当您转换 float 时，小数部分会被截断，即数字会向下舍入。因此，如果计算出的浮点值 k' 小于精确的 k，则将 k' 转换为整数将是 k - 1.

由于保证您得到的 float 与正确整数的误差很小，因此您可以通过舍入到最接近的整数而不是向下舍入来解决问题。 JSF 已经为此给出了算法:在向下舍入之前添加 0.5。

(*) 64 位 IEEE 754 float 可以表示精确到 10^17 的整数。

此外，还有一个潜在的结果大小问题。如果平台上int的大小是2个字节，那么k就会溢出。对于给定的 k 范围，一个 4 字节的 int 就足够了。您可以使用 int32_t 来保证必要的大小。