c++ - 计算两个数的超表中的第 N 个数

Question

两个数字表 a 和 b 被写入并按升序合并在一起，并删除重复项。现在的问题是在这个 super 表中找到比 O(n) 复杂度更好的 nth 数。

Limits 

1<=A, B<=1000

1<=N<=1000000000

这是我的实现，但它是O(n)，谁能推荐更好的复杂度算法？谢谢!

#include <iostream>
#include<map>
using namespace std;

long long int min(long long a, long long b){
    if(a<b) return a;
    else return b;
}

long long int get( long long int a,  long long int b,  long long int count) {
    long long int val = 0,i;
    long long int nexta = a;
    long long int nextb = b;
    for ( i = 0; i < count; i++) {
        val = min(nexta, nextb);
        nexta = val < nexta ? nexta : (nexta + a);
        nextb = val < nextb ? nextb : (nextb + b);
    }
    return val;
}


int main() {
    int t;
    cin >> t;

    while(t--){
        long long int a,b,n;
        cin >> a>> b>> n;
        cout << get(a,b,n)<< endl;
    }
    return 0;
}

示例:A=3, B=5

A = 3 , 6 , 9 , 12 ,15 ,18 等的表

B=5,10,15,20等的表

合并后:3, 5, 6, 9 ,10 , 12 ,15 ,15, 18, 20 等等

删除重复项:3、5、6、9、10、12、15、18、20 等等

对于 N= 2 ，超表的第二个元素是 5

Answer 1

如果我没看错，数组 A 和 B 指定如下:

A[i] = a*i
B[i] = b*i

然后通过应用二分查找至少可以得到 O(log N) 的解。

考虑一些值 x。它会不会超出您的第 n 元素？您需要确定 x 之前 union 序列中有多少元素。这很容易完成:从 A 开始有 x/a 元素，从 B 开始有 x/b，但是哎呀——我们已经计算了两次共同元素。有 x/d 个公共(public)元素，其中 d 是 a 和 b 的最不常见乘法，所以让我们减去x/d。所以如果x/a + x/b - x/d>=n，那么x至少是第n个元素，否则就是之前。

现在二进制搜索代码变成(伪代码)

l = 0
r = a * n + 1
d = lcm(a,b)
while r-l>1
    m = (r+l)/2
    cnt = m/a + m/b - m/d
    if cnt >= n
        r = m
    else l = m
your answer is r

也许甚至 O(1) 解决方案可用