主要内容 #

1. Blah数集
2. 算法分析
3. 参考代码

1. Blah数集 #

问题描述
大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下：
(1)a是集合Ba的基，且a是Ba的第一个元素；
(2)如果x在集合Ba中，则2x+1和3x+1也都在集合Ba中；
(3)没有其他元素在集合Ba中了。
现在小高斯想知道如果将集合Ba中元素按照升序排列，第N个元素会是多少？
输入描述
输入包括很多行，每行输入包括两个数字，集合的基a(1≤a≤50))以及所求元素序号n(1≤n≤1000000)。
输出描述
对于每个输入，输出集合Ba的第n个元素值。
输入样例
1 100
28 5437
输出样例
418
900585

2. 算法分析 #

题目要求输出集合中第n小的数，我们可以按照从小到大的顺序吧序列中的前n个数计算出来，注意数集中除了第一个数a外其余每一个数y一定可以表示成2x+1或者3x+1的形式，其中x是数集中某一个数。因此除了第一个数a外，可以把数集q[]的所有数分成两个子集，一个使用2x+1来表示的数的集合1，另一个是用3x+1来表示的数的集合2，两个集合保持有序非常容易，只需要两个指针two和three来记录，其中two表示集合1下一个要产生的数是由q[two]*2+1得到，three表示集合2下一个要产生的数是由q[three]*3+1得到。接下来比较q[two]*2+1和q[three]*3+1的大小关系：
（1）q[two]*2+1<q[three]*3+1：如果q[two]*2+1与q[rear-1]不等，则把q[two]*2+1加入数集中，即q[rear++]=q[two]*2+1;two++；
如果q[two]*2+1与q[rear-1]相等，因为集合的唯一性，q[two]*2+1不能加入数集，但two要加1。
（2）q[two]*2+1>=q[three]*3+1：处理方法同上。
如此循环直到产生了第n个数。

3. 参考代码 #

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000100;
long long q[N];
int a,n;
void work(int a, int n){
    int rear = 2;
    q[1] = a;
    int two = 1, three = 1;
    while(rear <= n){
        long long t1 = q[two] * 2 + 1, t2 = q[three] * 3 + 1;
        int t = min(t1, t2);
        if(t1 < t2) two++;
        else three++;
        if(t == q[rear-1]) continue;
        q[rear++] = t;
    }
    cout << q[n] << endl;
}

int main(){
    while(cin >> a >> n) work(a, n);
    return 0;
}