一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到M，凡报到M的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？ （注意：由于该问题规模显著提升，请扩展阅读“约瑟夫环”，理解更好的数学方法求解） 输入格式: 输入在一行中给两个正整数N, M（1<= N,M ≤10000000）。 输出格式: 在一行中输出当选猴王的编号。 用C语言解决上述问题

这是约瑟夫环问题，可以使用循环链表或数学方法求解。以下是使用数学方法的解法：

设有n个人（编号0~n-1），从0开始报数，报到(m-1)%n的人退出，剩下的人继续从0开始报数。求胜利者的编号。

设f(n,m)表示n个人玩游戏报到m退出最后胜利者的编号，最后的结果显然是f(n,m)，因为每次都是在n个人中删除第m个人，最后胜利者的编号就是f(n,m)。

如何推出f(n,m)和f(n-1,m)之间的关系？

首先先把编号改为0~n-1，方便计算，同时构建一个递推公式。f(n,m)表示每次删除一个人后剩下人的胜利者编号，显然有f(n,m)= (f(n-1,m)+m) % n。

如何知道最后胜利者在原始编号中的位置？

由于最后剩下一个人时退出的人在原始编号中的位置为0，所以最后胜利者在原始编号中的位置就是f(n,m)。