P4845 Blah数集（提高）

解题思路

**第一步，理解集合的生成规则。**集合Ba里第一个数是a，然后每个数x都会“生”出两个新数：2x+1 和 3x+1。把生成的数也放进集合，集合就越来越大。现在要求把集合里的数从小到大排好序，输出第n个。

**第二步，怎么能从小到大生成呢？**我们用一个数组q按从小到大的顺序保存已经生成的数，q[0]=a。再用两个“小箭头”p2和p3：p2指向还没有用来生成2x+1的那个数，p3指向还没有用来生成3x+1的那个数。因为数组是升序的，所以2q[p2]+1是所有“2x+1式”里最小的，3q[p3]+1是所有“3x+1式”里最小的，取这两者中更小的那个，就是下一个应该加入集合的数。

**第三步，处理重复的数。**有时2x+1和3y+1会算出同一个数，比如4可以由21+1=3和31+1=4得到（不重复），但也可能两边算出一样的数。遇到这种情况，哪个箭头的算式等于刚加入的数，就把哪个箭头往后移，这样才能保证集合里没有重复，而且不会漏数。

**第四步，注意数字会很大。**n最大是1000000，集合里的数会变得非常大，可能超过int能存的范围，所以要用long long来存数组。数组的长度就是n，开1000005个位置。

**举例子验证。**a=1时，前几个数是 1、3、4、7、9、10、13、15……其中1生成3和4，3生成7和10，4生成9和13……按升序排，第8个是15，和样例一致。

参考代码

// P4845 Blah数集：双指针生成第n小的元素，每个元素x产生2x+1和3x+1
#include <iostream>
#include <cstdio>
using namespace std;
int a, n;
long long q[1000005];  // 数组存升序的集合元素，n最大1000000
int main() {
    scanf("%d%d", &a, &n);
    q[0] = a;              // 基a是第一个元素
    int p2 = 0, p3 = 0, cnt = 1;
    while (cnt < n) {
        long long v2 = 2 * q[p2] + 1;  // 由2x+1产生的候选
        long long v3 = 3 * q[p3] + 1;  // 由3x+1产生的候选
        long long v = v2 < v3 ? v2 : v3;
        q[cnt++] = v;
        if (v2 == v) p2++;  // 指针前进，跳过重复
        if (v3 == v) p3++;
    }
    printf("%lld\n", q[n - 1]);
    return 0;
}

复杂度分析

每个数只被加入数组一次，两个箭头p2、p3最多各移动n次，所以总时间是O(n)。n最大是1000000，循环一百万次完全没问题。空间上需要一个能装下n个数的long long数组，约8MB内存，也足够。