这个题的数据量一看就是个数学题。。。然后就找啊找啊找规律！


一开始走错了方向，因为k=2

然后呢，找到了一个规律：（只对k=2适合）

第一轮的删掉的数：x%k=0

第二轮的删掉的数：x%k^2=k

第三轮的删掉的数：x%k^3=k^2

然后发现……

只对k=2适合

还是贴个程序纪念一下错误的数学思路吧


#include<bits/stdc++.h>
using namespace std;

#define LL __int64
LL calc(LL n,LL mod,LL left){
    LL x=n/mod;
    LL y=(n-(n/mod)*mod)>=left?1:0;
    return x+y;
}

int main(){
    //printf("%d\n",calc(24,2,1));
    //printf("%d\n",calc(24,4,2));
    //printf("%d\n",calc(24,8,4));
    //printf("%d\n",calc(24,16,8));
    //printf("%d\n",calc(24,32,16));
    //freopen("input.txt","r",stdin);
    int t;
    LL n,k,q;
    scanf("%d",&t);
    while(t--){
        scanf("%I64d%I64d%I64d",&n,&k,&q);
        LL mod,left,temp,x,thistime,num;
        while(q--){
            mod=1;left=0;
            thistime=temp=0;
            scanf("%I64d",&x);
            while(temp<x){
                left=mod;
                mod=mod*k;
                thistime=calc(n,mod,left);
                temp+=thistime;
            }
            num=thistime+x-temp-1;
            printf("%I64d\n",left+num*mod);
        }
    }
    return 0;
}

这个题的正确思路还是应该去打表

s【i】：i这个数是第几轮被删除的

t【i】：i这个数，在第s【i】轮中是第几个被删除的

如果知道这两个值，我们就可以打表了

首先分析第一轮，删去的都是%k为1的数

那么我们变成0~n-1，那么都是整除k的值

所以，如果不整除k呢，就可以往后放（相当于递推）

那么，在之前，删除了多少个数（相当于第一轮删除之后，原来的第i个值，放在了新数列的哪个位置）

顺着这个思路想，就得到了一个递推（说是DP也行）

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxn=3e6+50;
int s[maxn],t[maxn],sum[maxn],ans[maxn],tot;

int main(){
    //freopen("input.txt","r",stdin);
    int T,n,k,q,i,j;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&k,&q);
        memset(s,0,sizeof(s));
        memset(t,0,sizeof(t));
        memset(sum,0,sizeof(sum));
        memset(ans,0,sizeof(ans));
        tot=1;
        for(i=0;i<n;i++)
        if (i%k==0){
            s[i]=1;t[i]=i/k+1;sum[1]++;
            //ans[sum[1]]=i+1;
        }
        else{
            j=i-i/k-1;
            s[i]=s[j]+1;
            t[i]=t[j];
            sum[s[i]]++;
            tot=max(tot,s[i]);
        }
        for(int i=1;i<=tot;i++) sum[i]=sum[i]+sum[i-1];
        for(int i=0;i<n;i++)
            ans[sum[s[i]-1]+t[i]]=i+1;
        while(q--){
            scanf("%d",&k);
            printf("%d\n",ans[k]);
        }
    }
    return 0;
}