首先：暴力！40分

 略，大家都会

但是 暴力的另一个用处：打表！

 为什么打表呢？

 因为$2≤n,k≤10^{12}$。

 所以时间是O(1)。

 要找数学规律。

 打表：（输出的是没有被淘汰的人）

6 2  

1 2 3 4 5 6  

2 4 6  

4

8 3

1 2 3 4 5 6 7 8

2 3 5 6 8

3 5 8

5 8

8

注意到：每次剩下人中第一个人是有规律的，而且到最后一定只剩一个人（也是当前剩余人中的第一个），更重要的是，这个人的编号就是我们求的答案！！! 

设每次的第一个人依次是$x_1$,$x_2$,$x_3$,......,$x_m$。m是轮数。

则有$x_i+\lceil \frac{x_i}{k-1} \rceil=x_{i+1}$。

（这个需要自己找）

于是初始$x_1=1$ ，然后往后找。

#include<iostream>

using namespace std;

long long ans,n,k;//ans就是x

int main(){

   scanf("%lld%lld",&n,&k);

   ans=k;//前k个是依次作开头的，所以从k开始也一样

   while(ans+(ans+k-2)/(k-1)<=n){

       ans+=(ans+k-2)/(k-1);//套公式

   }

   printf("%lld",ans);//最后的开头就是最后一个人

   return 0;

}

嗯。于是就过关了！

But，洛谷上有个大佬出了个Hack，几乎把当时所有AC干成UAC了，这份代码也不例外。

就是这个  

1000000000000 10000000000

999999999907

会超时。  

分块优化：

于是我们继续想：每一轮都是一个人一个人淘汰的，所以我们对这一点进行优化…… 

因为$x_i+\lceil \frac{x_i}{k-1} \rceil=x_{i+1}$ ，所以按$k-1$分块（$k-1$分母，按$x_i$与$k-1$的关系分块，这样每个块的跳跃次数都是一样的)，批量跳跃被淘汰数。  

将整个数域$[1,n]$按每块$k−1$个数划分成若干块：  

第 $1$ 块：$[1,k−1]$  

第 $2$ 块：$[k,2(k−1)]$  

第 $id$ 块：$[(id−1)(k−1)+1,id(k−1)]$  

同一区块内的被淘汰数，递推的步长$\lceil \frac{x_i}{k-1} \rceil$是固定的（等于块编号 $id$），因此可以批量计算该块内的所有被淘汰数，一次跳跃，无需逐个计算。

在第$id$块中，$\lceil \frac{x_i}{k-1} \rceil$（$x$ 属于第 $id$ 块），因此递推式简化为：$x_{next}=x+id$

这意味着在第 $id$ 块中，被淘汰数是以$id$为步长递增的，可以直接计算出该块内最后一个被淘汰数，一次跳到下一块，大幅减少计算次数。

正片开始

#include<iostream>

#include<cstdio>

#include<cmath>

#define ll long long

using namespace std;

ll n,k;

ll x=1,last_val;//x为当前待检查的被淘汰数，初始为第一个被淘汰数x1=1

//last_val是当前块中最后被淘汰的数（答案），不断更新，最终输出

int main(){

   scanf("%lld%lld",&n,&k);

   while(x<=n){

       ll id=(x-1)/(k-1)+1;//是当前x所在块的编号

       ll end=min(n,(k-1)*id);//当前块的末尾

       x+=((end-x)/id+1)*id;//直接跳到当前块的末尾或跳出当前块

       last_val=x-id;//计算当前块最后一个淘汰的数，也可能是所有之中的最后一个淘汰的数（即答案）

   }

   printf("%lld",last_val);

   return 0;

}

OK