蓝桥杯-幸运数（模拟）_幸运数poj

幸运数：http://lx.lanqiao.org/problem.page?gpid=T33

直接按照题目意思模拟即可水过

本题也是官方数据太水，给定时间内无法完成 1 1000000 这个数据，想不到更快的算法了...

#include <cstdio>
 
using namespace std;
 
int m,n,cur,mod,sta,p,ans;//cur表示当前该处理的数字，sta表示这个数字的位置，p表示这个数字的前一个数字
int nxt[1000005];//数组模拟链表
 
void remov(int pre,int num,int cnt) {
    mod=num;
    while(num!=-1) {
        if(cnt==mod) {//如果当前数的位置能整除mod，则删除这个数，并将cnt置0
            nxt[pre]=nxt[num];
            cnt=0;
        }
        else//否则即将处理的数的前一个数变更
            pre=num;
        num=nxt[num];
        ++cnt;
    }
}
 
int main() {
    while(scanf("%d%d",&m,&n)==2) {
        for(int i=1;i<n;++i) {
            nxt[i]=i+1;
        }
        nxt[n-1]=-1;//由于不能等于m和n，所以链表表尾为n-1，这样可以减少后面判断
        p=1;
        sta=cur=2;//从数字2开始模拟题目所述操作
        while(cur!=-1) {
            remov(p,cur,sta);
            if(sta!=cur) {//如果当前数的位置不等于其值，则p和sta均改变
                p=cur;
                ++sta;
            }
            cur=nxt[cur];
        }
        ans=0;
        for(int i=1;i!=-1;i=nxt[i]) {
            if(m<i) {
                ++ans;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}