两个数字的倍数列表的第n个数字

Question

几个月前在亚马逊招聘挑战中遇到了这个问题。 给出两个数字a和b以及它们的倍数列表按升序排列，找到nth倍数。

例如，如果a = 4 , b = 6和n = 6然后回答是18，因为列表是4 6 8 12 16 18 20 24 28 30....

这是我使用的方法：

1. 选择较小的a和b。将它分配给小。将另一个分配给大。
2. 生成a和b的倍数到small*n的列表（如上所示），因为所需的答案不能大于此。
3. 创建指向此列表中最后一个数字的指针。
4. 将此指针移回更大数字的倍数，直到small*n（简单地通过(small * n)/big收回指针）。
5. 将指针向前移动a和b的最小公倍数，直到small * n。这是必需的答案。

这种方法在小型测试用例上运行良好，但在较大的测试用例上则有效。

请建议一个较短时间复杂的方法。由于某些原因，Mathjax不能在我的任何浏览器中工作。

Answer 1

注意到，找到L=LCM(a,b)（这里12） 还计算la = LCM/a, lb = LCM/b（这里3,2） 注意，L代表行中的F = la + lb - 1-th，而LCM的第k个多数位于k * F-th的序列位置（此处为k * 4） 所以你可以很容易地找到： -interval，其中第n个成员是：idx = n div F（这里6 div 4 = 1从0开始） -place在这个区间：p = div mod F（这里6 mod 4 = 2从0开始）

现在你必须找到0..LCM - 1范围内的第p项。请注意，您不需要构建列表（可能的方法 - 二进制搜索）

Answer 2

考虑到任意自然n的倍数是floor(n / a) + floor(n / b) - floor(n / lcm(a, b))，我们可以进行简单的二分搜索。然后用较小的result mod a或result mod b减去结果。

JavaScript代码：

function gcd(a,b){
  while (b > 0)
    [a, b] = [b, a % b];

  return a;
}

function lcm(a, b){
  return a * b / gcd(a, b);
}

function countMul(a, b, lcmAB, n){
  return ~~(n / a) + ~~(n / b) - ~~(n / lcmAB);
}

function nthMul(a, b, n){
  let low = Math.min(a,b);
  let high = n * Math.min(a,b);
  let mid = ~~((low + high) / 2);
  let lcmAB = lcm(a, b);
  
  while (countMul(a, b, lcmAB, mid) != n){
    if (countMul(a, b, lcmAB, mid) > n)
      high = mid;
    else
      low = mid;
    
    mid = ~~((low + high) / 2);
  }
  
  return mid - Math.min(mid % a, mid % b);
}

console.log(nthMul(4,6,6));