c++ - 给定 (a, b) 计算 k 的最大值，使得 a^{1/k} 和 b^{1/k} 是整数

Question

我正在编写一个程序，试图找到 k > 1 的最小值，使得 a 和 b(均已给定)的第 k 个根等于整数。

这是我的代码片段，我已对其进行评论以进行说明。

int main()
{
    // Declare the variables a and b.
    double a;
    double b;
    // Read in variables a and b.
    while (cin >> a >> b) {

        int k = 2;

        // We require the kth root of a and b to both be whole numbers.
        // "while a^{1/k} and b^{1/k} are not both whole numbers..."
        while ((fmod(pow(a, 1.0/k), 1) != 1.0) || (fmod(pow(b, 1.0/k), 1) != 0)) {

        k++;

        }

差不多，我读入 (a, b)，然后我从 k = 2 开始递增 k，直到 a 和 b 的第 k 个根都等于 0 mod 1(这意味着它们可以被 1 整除，因此整数)。

但是，循环无限运行。我试过研究，我认为这可能与精度误差有关；但是，我不太确定。

我尝试过的另一种方法是更改​​循环条件以检查 a^{1/k} 的下限是否等于 a^{1/k} 本身。但同样，这会无限运行，可能是由于精度错误。

有谁知道我该如何解决这个问题？

编辑:例如，当 (a, b) = (216, 125) 时，我希望 k = 3，因为 216^(1/3) 和 125^(1/3) 都是整数(即， 5 和 6)。

Answer 1

这不是编程问题，而是数学问题:

if a is a real, and k a positive integer, and if a^(1./k) is an integer, then a is an integer. (otherwise the aim is to toy with approximation error)

所以最快的方法可能是首先检查 a 和 b 是否为整数，然后执行 prime decomposition这样 a=p₀^e₀ * p₁^e₁ * ...，其中 p_i 是不同的素数。

请注意，要使 a^1/k 成为整数，每个 e_i 也必须能被 k 整除。换句话说，k 必须是 e_i 的公约数。如果 b^1/k 是一个整数，则 b 的素数幂也必须如此。

因此最大的 k 是 greatest common divisor a 和 b 的所有 e_i。

---

使用您的方法，您将遇到大量问题。所有 IIEEE 754 binary64 浮点(x86 上 double 的情况)都有 53 个有效位。这意味着所有大于 2⁵³ 的 double 都是整数。

函数 pow(x,1./k) 将对两个不同的 x 产生相同的值，因此使用您的方法，您必然会得到错误的答案，例如数字 5⁵*2⁹⁰ 和 3⁵*2¹²⁰ 可以用 double 表示。算法的结果是k=5。您可能会发现这些数字的 k 值，但您还会发现 k=5 5⁵*2⁹⁰-2⁴⁹ 和 3⁵*2¹²⁰, 因为 pow(5⁵*2 ⁹⁰-2⁴⁹,1./5)==pow(5⁵*2⁹⁰)。演示 here

另一方面，由于只有 53 个有效位，所以 double 的素数分解是微不足道的。