如何找到除数以最大化余数？

Question

给出两个数字,n并k找到x,1 <= x <= k最大化余数n % x.

例如,n = 20且k = 10,解是x = 7,因为余数20%7 = 6是最大的.

---

我的解决方案是:

int n, k;
cin >> n >> k;
int max = 0;
for(int i = 1; i <= k; ++i)
{
  int xx = n - (n / i) * i; // or int xx = n % i;
  if(max < xx)
    max = xx;
}
cout << max << endl;

但我的解决方案是O(k).有没有更有效的解决方案？

Answer 1

不是渐近更快,而是更快,只需通过倒退并在您知道自己无法做得更好时停下来.

假设k小于n(否则只是输出k).

int max = 0;
for(int i = k; i > 0 ; --i)
{
  int xx = n - (n / i) * i; // or int xx = n % i;
  if(max < xx)
    max = xx;
  if (i < max)
    break;   // all remaining values will be smaller than max, so break out!
}
cout << max << endl;

(这可以通过执行for循环来进一步改进i > max,从而消除一个条件语句,但我这样写它以使其更明显)

另外,检查Garey和Johnson的计算机和难以处理的书,以确保这不是NP-Complete(我确信我记得那本看起来很像这本书的问题).在投入太多精力试图找到更好的解决方案之前,我会这样做.

Answer 2

这个问题相当于f(x)=n%x在给定范围内找到最大函数.让我们看看这个函数是怎样的:

显而易见的是,如果我们开始时可以更快地获得最大值x=k,然后x在有意义的情况下减少(直到x=max+1).此图也显示,对于x大于sqrt(n)我们不需要x按顺序减少.相反,我们可以立即跳到前一个局部最大值.

int maxmod(const int n, int k)
{
    int max = 0;

    while (k > max + 1 && k > 4.0 * std::sqrt(n))
    {
        max = std::max(max, n % k);
        k = std::min(k - 1, 1 + n / (1 + n / k));
    }

    for (; k > max + 1; --k)
        max = std::max(max, n % k);

    return max;
}

Magic常量4.0允许通过减少第一(昂贵)循环的迭代次数来提高性能.

最坏情况时间复杂度可以估计为O(min(k,sqrt(n))).但是对于足够大的k估计可能过于悲观:我们可以更快地找到最大值,并且如果k明显大于sqrt(n)我们只需要1或2次迭代就可以找到它.

我做了一些测试来确定在最坏的情况下需要多少次迭代以获得不同的值n:

    n        max.iterations (both/loop1/loop2)
10^1..10^2    11   2   11
10^2..10^3    20   3   20
10^3..10^4    42   5   42
10^4..10^5    94  11   94
10^5..10^6   196  23  196
up to 10^7   379  43  379
up to 10^8   722  83  722
up to 10^9  1269 157 1269

增长率明显优于O(sqrt(n)).