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

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 的 Computers and Intractability 一书，以确保这不是 NP-Complete(我确定我记得那本书中的一些问题看起来很像这样)。在投入太多精力试图提出更好的解决方案之前，我会这样做。