我正在编写一个程序,试图找到 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)。
最佳答案
这不是编程问题,而是数学问题:
if
a
is a real, andk
a positive integer, and ifa^(1./k)
is an integer, thena
is an integer. (otherwise the aim is to toy with approximation error)
所以最快的方法可能是首先检查 a
和 b
是否为整数,然后执行 prime decomposition这样 a=p0e0 * p1e1 * ...,其中 pi 是不同的素数。
请注意,要使 a1/k 成为整数,每个 ei 也必须能被 k 整除。换句话说,k 必须是 ei 的公约数。如果 b1/k 是一个整数,则 b 的素数幂也必须如此。
因此最大的 k
是 greatest common divisor a
和 b
的所有 ei。
使用您的方法,您将遇到大量问题。所有 IIEEE 754 binary64 浮点(x86 上 double 的情况)都有 53 个有效位。这意味着所有大于 253 的 double 都是整数。
函数 pow(x,1./k)
将对两个不同的 x
产生相同的值,因此使用您的方法,您必然会得到错误的答案,例如数字 55*290 和 35*2120 可以用 double 表示。算法的结果是k=5
。您可能会发现这些数字的 k
值,但您还会发现 k=5
55*290-249 和 35*2120, 因为 pow(55*2 90-249,1./5)==pow(55*290)。演示 here
另一方面,由于只有 53 个有效位,所以 double 的素数分解是微不足道的。
关于c++ - 给定 (a, b) 计算 k 的最大值,使得 a^{1/k} 和 b^{1/k} 是整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54008802/