UVa 1452 - Jump(約瑟夫環變形)

題意
把1～n按逆時針順序排成一個圓圈，從1開始沒k個數字刪除掉一個，知道所有數字都刪完。

求最後刪除的3個數。

思路
我們已經知道了，怎麼可以推出最後一個被刪除的編號（可參考百度百科）

f(1) = 0, 表示最後還剩下一個時，這個編號為0

f(n) = (f(n-1) + m) % n

那麼保存最後第1,2,3個數，一直推到第一個即可。

代碼

/**========================================== * 
  This is a solution for ACM/ICPC problem * 
 *   @source:  uva-1452 Jump *  
 @author: shuangde * 
  @blog: blog.csdn.net/shuangde800 * 
  @email: [email protected] *===========================================*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f;
const double PI  = acos(-1.0);
const int MAXN = 110;
int n, m;
int main(){    int T;  
  scanf("%d", &T);  
  while(T--){                scanf("%d%d", &n, &m);    
    int ans1 = 0, ans2, ans3;     
   for(int i=2; 
i<=n; 
++i){            ans1 = (ans1+m) % i;    
        if(i==2){                
// 當剩下最後2個數時，編號為0，1, 推出倒數第二個刪除的數當前值                ans2 = !ans1;  
          }else if(i==3){           
     // 當剩下最後3個數時，編號為0，1，2, 推出倒數第三個刪除的數當前值                ans2 = (ans2+m) % i;   
             bool vis[3];        
        memset(vis, 0, sizeof(vis));  
              vis[ans1] = vis[ans2] = true;  
              for(int j=0;
 j<3; 
++j)if(!vis[j]){                    ans3 = j; 
break;        
         }            }else{                ans2 = (ans2+m) % i;  
              ans3 = (ans3+m) % i;         
   }        }        ans1 = (ans1+1)%n;     
    ans2 = (ans2+1)%n;     
   ans3 = (ans3+1)%n;     
   printf("%d %d %d\n", ans3?ans3:n, ans2?ans2:n, ans1?ans1:n);   
 }    return 0;}