10

我有两个数字，x1和x2。对于一个数字y，我想计算x1和x2尽可能接近的公约数y。

有没有一个有效的算法呢？

我相信是时候重新表述我的问题并更清楚了。这与整数无关......所以，假设我们有两个数字x1和x2。比如说，用户输入了一个数字y。我想要找到的是一个y'接近的数字y，x1 % y'并且非常小（例如，x2 % y'小于，但让我们称之为这个数字）。换句话说，我不需要一个最佳算法，而是一个很好的近似值。0.02LIMIT

我感谢大家的时间和精力，真是太好了！

4

4 回答 4

7

我相信对于这个问题没有已知的有效（多项式时间）算法，因为从整数分解到这个问题存在多项式时间减少。由于没有已知的用于整数分解的多项式时间算法，因此也不存在针对您的问题的已知算法，因为否则我们确实会有用于整数分解的多项式时间算法。

要了解它是如何工作的，假设您有一个想要分解的数字 n。现在，使用您喜欢的任何算法，找到最接近 √n 的 n 和 n 的公因数。由于 n 的任何非平凡除数都不能大于 √n，因此可以找到 (1) 除以 n 的最大整数，或者 (2) 如果 n 是素数，则找到数字 1。然后，您可以将 n 除以该数字并重复以产生 n 的所有因数。由于 n 最多可以有 O(log n) 因子，因此对于您的问题，这最多需要多项式多次迭代求解器，因此我们从整数分解到这个问题的多项式时间减少。如上所述，这意味着，至少在公开文献中，没有已知的有效经典算法来解决这个问题。一个可能存在，但这将是一个非常重要的结果。

对不起，否定的答案，希望这会有所帮助！

于 2012-02-08T19:23:48.543 回答
2

我认为您可以通过贪心算法来做到这一点，首先通过常用算法命名它d（可以以对数时间计算）找到 GCD，然后找到d每个时间的因子除以d最小的可用因子（创建d'），并|d'-y|与|d-y|if 较小的 continue 在此进行比较方式（并替换d'为d），否则，乘以d'最小消除因子，并再次比较其与 y 的距离。

于 2012-02-08T18:02:40.743 回答
2

这是有效的，因为我可以得到它：

from fractions import gcd
primes=[i for i in range(2,1000) if all(i%j!=0 for j in range(2,i))] #ensure you have enough primes.. (can improve efficency here)


def f(x1,x2,y):
    _gcd=gcd(x1,x2)
    if _gcd==1:
        return 1
    factors=(i for i in range(2,_gcd+1) if _gcd%i==0) #can improve efficiency here.. e.g. only go up to root(gcd)
    r1=999999999
    r2=999999999
    for i in factors:
        r1=min(r1,y%i)
        r2=min(r2,i-y%i)
    return y-r1 if r1<=r2 else y+r2


print f(8,4,3)
print f(16,12,5)
print f(997,53,44)
print f(2300*2,2300*3,57)

"""
2
4
1
56
"""
于 2012-02-08T21:13:15.073 回答
0
  1. 求 和 的x1GCD x2。
  2. 如果GCD <= Y然后返回GCD
  3. 当前最佳答案是GCD，最佳距离为GCD - y。
  4. 遍历所有数字 Y +/- [0 ... 最佳距离]
  5. 返回第一个整数是两者的x1倍数x2

寻找 GCD

public int getGCD( int a, int b )
{
   return (b==0) ? a : gcd(b, a%b);
}

要找到最接近 y 的除数...

public int closestDivisor( int a, int b, int y ){
    int gcd = getGCD( a, b );
    if( gcd <= y ) return gcd;
    int best = gcd - y;
    for( int i = 0; i < best; i++ )
    {
        if( gcd % (i-y) == 0 ) return i - y;
        if( gcd % (i+y) == 0 ) return i + y;
    }
    return gcd;
}

我相信唯一可用的额外优化是按照@trinithis 的建议考虑gcd（也许使用筛子？）。

于 2012-02-08T18:02:00.753 回答