【简单模拟+哈希】HDU-1216 Assistance Required

注解

1、第一个数字是2，然后每次跳过1个数字，将第2的整数倍的自然数：4、6、8这些数字删除；第二次变为，第一个数字是3，然后每次跳过2个数字，将第3的整数倍的自然数：9（跳过5、7），15（跳过11、13）这些数字删除。依次类推。
2、采用Hash的手段，进行模拟。

代码

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int MAXN = 35000;
const int SIZE = 3001;
int a[MAXN];
vector<int> v;

void preprocess() {
    v.push_back(1);
    memset(a, 0, sizeof(a));
    while(v.size()<SIZE) {
        int now = v.at(v.size()-1)+1;
        for(int i=now; i<MAXN; i++) {
            if(a[i]==0) {
                now = i;
                a[i] = 1;
                break;
            }
        }
        v.push_back(now);
        int count = 0;
        for(int i=now+1; i<MAXN; i++) {
            if(a[i]==0) {
                count++;
                if(count%now==0) {
                    a[i] = 1;
                }
            }
        }
    }
}

int main() {

    preprocess();

    int n;
    cin>>n;
    while(n) {
        cout<<v.at(n)<<endl;
        cin>>n;
    }

    return 0;
}

结果