传送门 这道题就是规律不是很好推,我们像分析约瑟夫环那样，每次只看最后一个被杀人的在当前人数中的编号，然后在回溯回去，找到在n个人中被杀人的编号 我们拿样例来举例 第一轮：1，2，3，4，5，6，7，8，9，10 编号： 1，2，3，4，5，6，7，8，9，10 经过第一轮后 第二轮：1，2，3，4，5，6，7，8，9，10 编号： 1，2，\，3，4，\，5，6，\，7 （3，6，9）被杀 我们可以看到第二轮中最后一个死的土匪编号为6（在原来n个土匪的编号是8）那么如何从6得到8呢；我们必须知道6之前在第一轮中死了多少人，为解决这个问题，我们换一下条件： 已知第二轮式编号为1，2，3，4，5，6，n=10,k=3,要求推出第一轮的编号，这个就很好想，我们知道每隔k-1个数我们就要杀一个，所以2后面我们杀了一个，4后杀了一个,6后杀了一个，也就是1，2，\，3，4，,5，6，\，\（因为有10个人，所以最后还要添一个人）所以我们只要看编号6前面的5个人分成k-1(也就是2)组有多少组（这里是2）那么第二轮中编号为6的人在第一轮的编号就是6+2=8； 所以有结论：已知第x轮时最后一个被杀的编号为a,那么在第x-1轮时它的编号就是a+(a-1)/(k-1); 这样我们如果已知最后一个人被杀的轮数dep和他的编号（很容易知道这一轮中他的编号一定是K）那么我们就可以经过dep轮的回推求出他一开始的编号。 一开始我傻了，我把每一轮被杀的最后一个人的编号都求出来，然后又T又Wa的。。实际上只需要最后一个人的。 代码：
#include<iostream> #include<algorithm> #include<vector> #include<set> #include<time.h> #include<cmath> #include<cstring> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<functional> #include<stack> #include<map> #include<queue> #define mod (1000) #define middle (l+r)>>1 #define SIZE 10000+10 //#define lowbit(x) (x&(-x)) #define lson (rt<<1) #define rson (rt<<1|1) typedef long long ll; const int inf_max = 0x3f3f3f3f; const ll Linf = 9e18; const int maxn = 100000+10; const double eps=0.0001; using namespace std; ll n,k; int main() { int t; scanf("%d",&t); while(t--) { scanf("%lld%lld",&n,&k); ll now=n,ans,dep=0,last=k; while(now>=k) //一共经过多少论导致死到只有k-1个人 { dep++; now-=now/k; } while(--dep) { last+=(last-1)/(k-1);//回溯编号 } printf("%lld\n",last); } return 0; }