Gym - 101955K Let the Flames Begin 约瑟夫环

Gym - 101955K Let the Flames Begin 

说实话，没怎么搞懂，直接挂两博客。

小飞_Xiaofei的约瑟夫问题（Josephus Problem）3：谁最后一个出列

 小飞_Xiaofei的约瑟夫问题（Josephus Problem）4：第k个出列的人是谁

 林夕-梦的约瑟夫环问题 （ 最简单的数学解法）

等真正搞明白再来理一理思路，现在直接将讲一下流程。

约瑟夫环题目就是n个人轮流报数，报到k的出列，然后接着重新从1开始报，再报到k的出列。

求最后一个出列的人便是，设ans=0,然后for(int i=1;i<=n;i++) ans=(ans+k)%i，最后ans+1

而求第m个出列的人便是，设m=n+1-m ans=(k-1)%m for(int i=m+1;i<=n;i++) ans=(ans+k)%i,最后ans+1

然后当n,m,k都很大，但min(m,k)挺小时，便是这题的情况，便把用区间跳跃的思想，把一些不用取模的加法合并成一个乘法。

csu_xiji的codeforces gym101955 K Let the Flames Begin 约瑟夫环问题

 1 #include<cstdio>
 2 typedef long long ll;
 3 int main(){
 4     int t=1,T;
 5     ll n,m,k;
 6     scanf("%d",&T);
 7     while(t<=T){
 8         scanf("%lld%lld%lld",&n,&m,&k);
 9         ll ans,d,p;
10         if(k==1) ans=m-1;
11         else{
12             m=n+1-m;
13             ans=(k-1)%m;
14             if(n+1-m<=k){
15                 p=m+1;
16                 while(p<=n){
17                     ans=(ans+k)%p;
18                     p++;
19                 }
20             }else{
21                 p=m;
22                 while(true){
23                     d=(p-ans)/(k-1);
24                     if(d*(k-1)==(p-ans)) d--;
25                     if(d>n-p) d=n-p;
26                     p+=d;
27                     ans+=d*k;
28                     if(p==n) break;
29                     p++;
30                     ans=(ans+k)%p;
31                     if(p==n) break;
32                 }
33             }
34         }
35         printf("Case #%d: %lld\n",t++,ans+1);
36     }
37     return 0;
38 } 

题解做题法