题目链接：

　　其实基本就是约瑟夫环问题，最终accepted的answer是看过相关资料才写出来的：

 

　　无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂 度高达O(nm)，

当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

 

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:

k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2 并且从k开始报0。 现在我们把他们的编号做一下转换：

k --> 0

k+1 --> 1

k+2 --> 2

... ...

k-2 --> n-2

k-1 --> n-1

　　变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：

例如x是最终的胜利者，那么根 据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！

变回去的公式很简单，相信大家都可以推出来：

x=(x+k)%n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的 情况 ---- 这显然就是一个倒推问题！

代码：Accepted：

1 #include
     
       2 #define MAX 100 3  4 using namespace std; 5  6 int main(){ 7     int n = 1, k = 1, m = 1, cnt =0; 8     int rel[MAX] = { 0 }; 9     while((n!=0) && (k!=0) && (m!=0))10     {11         cin >> n >> k >> m;12          if((n!=0) && (k!=0) && (m!=0))13         {14             int f=0;15             for(int i=2;i
      
       < cnt;i++)23     {24         cout << rel[i] << endl;25     }26     return 0;27 }
      
     

　　我用链表写的，总超时，后面我对其进行了很多优化，也通不过，我怀疑只能通过数学解法做，也列出来吧

　　链表的约瑟夫问题太有名了，以至于我神马都没想，就直接用链表做了

1 #include 
     
       2 #define MAX 100 3 using namespace std; 4  5 typedef struct node 6 { 7     int num; 8     node* nxt; 9 }node;10 typedef node* Lst;11 12 int Final(int n, int k, int m);13 14 int main()15 {16     int n = 1, k = 1, m = 1, cnt =0;17     int rel[MAX] = { 0 };18     while((n!=0) && (k!=0) && (m!=0))19     {20         cin >> n >> k >> m;21         if((n!=0) && (k!=0) && (m!=0))22         {23             rel[cnt] = Final(n,k,m);24             cnt++;25         }26 27     }28 29     for(int i = 0;i < cnt;i++)30     {31         cout << rel[i] << endl;32     }33 34      /*for(int i = 0; i < 2*n;i++)35     {36         cout << head->num<
      
       nxt;38     }*/39 40     return 0;41 }42 int Final(int n, int k, int m)43 {44     Lst L, head, tmp;45     L = new node;46     L->nxt = L;47     head = L;48     L->num = 1;49 50     for(int i = 1; i < n;i++)51     {52         //Insert(L, i+1)53         tmp = new node;54         tmp->num = i+1;55         head->nxt = tmp;56         tmp->nxt = L;57         head = tmp;58         //cout << head->num << " \t";59     }60     int stonecnt = n;61     head = L;62     for(int i = 0;i < (m-1)%n; i++)63     {64         tmp =head;65         head = head->nxt;66     }67     stonecnt--;68     Lst del = head;69     head = head->nxt;70     tmp->nxt = head;71     delete del;72     while(stonecnt > 1)73     {74         for(int i = 0;i < (k-1)%stonecnt; i++)75         {76             tmp =head;77             head = head->nxt;78         }79         stonecnt--;80         del = head;81         head = head->nxt;82         tmp->nxt = head;83         delete del;84     }85     int rel = head->num;86     delete head;87     return rel;88 }