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

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

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

最佳答案

如果我理解正确，请按照以下方式指定arays A和B:

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

那么您可以通过应用二进制搜索至少获得O(log N)解决方案。

考虑一些值x。它会超出您的n元素吗？您需要确定x之前联合序列中有多少个元素。这很容易做到:从A中有x/a元素，从B中有x/b，但是糟糕-我们计算了两次常见元素。有x/d公用元素，其中d是a和b的最小公倍数，因此让我们减去x/d。因此，如果x/a + x/b - x/d>=n，则x至少是n th元素，否则它在之前。

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

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)解决方案都可用

关于c++ - 计算两个数字的超表中的第N个数字，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30352036/