给定(a，b)计算k的最大值，使得a ^ {1/k}和b ^ {1/k}是整数 [英] Given (a, b) compute the maximum value of k such that a^{1/k} and b^{1/k} are whole numbers

问题描述

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

I'm writing a program that tries to find the minimum value of k > 1 such that the kth root of a and b (which are both given) equals a whole number.

这是我的代码的一部分，我已对其进行注释以供澄清.

Here's a snippet of my code, which I've commented for clarification.

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整除，因此整数).

Pretty much, I read in (a, b), and I start from k = 2 and increment k until the kth roots of a and b are both congruent to 0 mod 1 (meaning that they are divisible by 1 and thus whole numbers).

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

But, the loop runs infinitely. I've tried researching, and I think it might have to do with precision error; however, I'm not too sure.

我尝试过的另一种方法是更改​​循环条件，以检查a ^ {1/k}的底限是否等于a ^ {1/k}本身.但这又是无限的，可能是由于精度误差造成的.

Another approach I've tried is changing the loop condition to check whether the floor of a^{1/k} equals a^{1/k} itself. But again, this runs infinitely, likely due to precision error.

有人知道我该如何解决这个问题?

Does anyone know how I can fix this issue?

例如，当(a，b)=(216，125)时，我想让k = 3，因为216 ^(1/3)和125 ^(1/3)都是整数(即， 5和6).

for example, when (a, b) = (216, 125), I want to have k = 3 because 216^(1/3) and 125^(1/3) are both integers (namely, 5 and 6).

推荐答案

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

That is not a programming problem but a mathematical one:

如果a是实数，并且k是正整数，并且a^(1./k)是整数，则a是整数. (否则，目的是使玩具具有近似误差)

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是否为整数，然后执行

So the fastest approach may be to first check if a and b are integer, then do a prime decomposition such that a=p₀^e₀ * p₁^e₁ * ..., where p_i are distinct primes.

请注意，对于a ^1/k 为整数，每个e _i 也必须可被k整除.换句话说，k必须是e _i 的公因数.如果b ^1/k 为整数，则b的质数必须相同.

Notice that, for a^1/k to be an integer, each e_i must also be divisible by k. In other words, k must be a common divisor of the e_i. The same must be true for the prime powers of b if b^1/k is to be an integer.

因此，最大的k是所有e _中的最大公约数. a和b的i .

Thus the largest k is the greatest common divisor of all e_i of both a and b.

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

With your approach you will have problem with large numbers. All IIEEE 754 binary64 floating points (the case of double on x86) have 53 significant bits. That means that all double larger than 2⁵³ are integer.

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

The function pow(x,1./k) will result in the same value for two different x, so that with your approach you will necessary have false answer, for example the numbers 5⁵*2⁹⁰ and 3⁵*2¹²⁰ are exactly representable with double. The result of the algorithm is k=5. You may find this value of k with these number but you will also find k=5 for 5⁵*2⁹⁰-2⁴⁹ and 3⁵*2¹²⁰, because pow(5⁵*2⁹⁰-2⁴⁹,1./5)==pow(5⁵*2⁹⁰). Demo here

另一方面，由于只有53个有效位，因此double的质数分解是微不足道的.

On the other hand, as there are only 53 significant bits, prime number decomposition of double is trivial.

这篇关于给定(a，b)计算k的最大值，使得a ^ {1/k}和b ^ {1/k}是整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！