心路历程：
一、注意到 \(min(m,k)\) 条件，分别考虑。
①当 \(m\) 很小时，直接 \(O(m)\) 递归求解。
②当 \(k\) 很小时，每次批量处理 \(\lfloor \frac{n}{k}\rfloor\) 个，同样递归，时间复杂度为 \(O(\log_{1-\frac{1}{k}}^{n}) \approx 9e^7\)，绰绰有余。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define N 2000000
ll work2(ll n,ll m,ll k){
if(m==0)return 0;
return (k+work2(n-1,m-1,k)-1)%n+1;
}
ll work(ll n,ll m,ll k){
if(m==0)return 0;
if(m<=N){
return (k+work(n-1,m-1,k)-1)%n+1;
}
ll cnt=n/k;
if(cnt==0)return work2(n,m,k);
if(cnt>=m)return m*k;
ll nex=work(n-cnt,m-cnt,k)-(n-cnt*k);
if(nex<=0)return (nex+n-1)%n+1;
ll now=(nex-1)/(k-1);
return nex+now;
}
int main(){
int t;cin>>t;
for(int i=1;i<=t;++i){
cout<<"Case #"<<i<<": ";
ll n,m,k;cin>>n>>m>>k;
cout<<work(n,m,k)<<endl;
}
return 0;
}
二、死命 \(RE,TLE\) ，意识到递归开不了这么大的栈。。。把 ① 改完后发现 ② 不好改。遂放弃，去看题解。
三、半改半抄后还是 \(WA\)，经过找不同后发现我写的是
\[pos=(pos+k-1)\%n+1 \]题解写的是
\[pos'=(pos'+k)\%n \]才发现实际上应该写成
\[pos-1=(pos-1+k)\%n \]这样就能让取模最后执行，方便把加法合并成乘法。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll work1(ll n,ll m,ll k){
ll pos=-1,nn=n-m;
while(nn<n){
++nn;pos=(pos+k)%nn;
}
return pos+1;
}
ll work2(ll n,ll m,ll k){
if(k==1)return m;
ll pos=-1,nn=n-m,t;
while(nn<n){
t=min((nn-pos)/(k-1),n-1-nn);
if(t){
nn+=t;
pos=(pos+t*k)%(nn);
}
++nn;
pos=(pos+k)%nn;
}
return pos+1;
}
int main(){
int t;cin>>t;
for(int i=1;i<=t;++i){
ll n,m,k;cin>>n>>m>>k;
cout<<"Case #"<<i<<": ";
if(m<k)cout<<work1(n,m,k)<<endl;
else cout<<work2(n,m,k)<<endl;
}
return 0;
}