资源限制

时间限制：1.0s 内存限制：256.0MB

　　n 个人的编号是 1~n，如果他们依编号按顺时针排成一个圆圈，从编号是1的人开始顺时针报         数。
　　（报数是从1报起）当报到 k 的时候，这个人就退出游戏圈。下一个人重新从1开始报数。
　　求最后剩下的人的编号。这就是著名的约瑟夫环问题。

　　本题目就是已知 n，k 的情况下，求最后剩下的人的编号。

　　题目的输入是一行，2个空格分开的整数n, k
　　要求输出一个整数，表示最后剩下的人的编号。

　　约定：0 < n,k < 1百万

　　例如输入：
　　10 3

　　程序应该输出：
　　4

题目分析：

由于输入的数字数据太大，达到百万，正常的链表计算约瑟夫圆环肯定超时，那么我们可以用递推的方式进行求解。

递推公式

                            

f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号。
f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号。

下面我们不用字母表示每一个人，而用数字。
                        1、2、3、4、5、6、7、8、9、10、11

表示10个人。他们先排成一排，设定报数3的人出局。

刚开始的时候，从编号1开始报数，第一轮出局的是是编号3。

第一轮过后，编号为4的人报1，第二轮出局的是编号6。

第二轮过后，编号为7的人报1，第三轮出局的是编号9。

第三轮过后，由于总共是11人,编号10报数1，编号11报数2，编号1报数3，编号1出局。

依次类推，游戏胜出者就是编号7。

下图表示这一过程（先忽视绿色的一行）

 现在我们来推导一下这个递推公式

将上面表格的每一行看成数组，这个公式描述的是：游戏胜出者在这一轮的数组下标位置

f(1,3)=0：只有一个人，这个人就是游戏胜出者，此时他的下标位置是0

f(2,3)=(f(1,3)+3)%2=3%2=1：在有2个人的时候，胜出者的下标位置是1

f(3,3)=(f(2,3)+3)%3=4%3=1：在有3个人的时候，胜出者的下标位置为1

f(4,3)=(f(3,3)+3)%4=4%4=0：在有4个人的时候，胜利者的下标位置为0

·······

最后 f(11,3)=6 （注意此时得到的是数组下标位置，最后应该+1才是编号） 

下面将讲解怎么推导这个公式。

1、假设我们知道了11人的时候，胜出者的下标位置是6，那么经过第一轮游戏之后，剩下10个人，应该是3，是向前移动了3位，为什么呢，因为前一轮已经走过了三个人，在走过了上一轮之后，原本报4的人，反而成了报1的人，所以得到胜出位置的这个3就是之前的6往前移动了3位。（此时也需要考虑数组越界问题，由于我们是用递推公式，在下一个假设中利用公式的取模即可）

2、同理倒着思考，假设知道了10个人的时候，胜出者的下标位置是3，有11个人的时候，同理推出他的下标位置应该向后移动3位，也就是加上3。但是因为数字的长度有限制，肯定不能让数组越界，所以要取模，得到数组位置，所以是f(11,3)=（f(10,3)+3）%11。

3.根据上面两点，此时整体看这个公式，此时有N个人，报数为M的出局，那么此时的数组应该是怎么移动的呢？

开局时，胜出者的位置是：f(N,M)=（f(N-1,M)+M）%N

当出局一人的时候，他的下一个人成为头部，报数1，此时相当于原数组向前移动了M个位置，此时有N-1个人，此时胜出者的位置是f(N-1,M)=（f(N-2,M)+M）%（N-1）,依次类推，因为f(1,M)=1是一定的，这是递推的初始条件，那么我们就可以根据公式得出最后胜出者的位置。

理解这个递推式的核心在于关注胜出者的下标位置是怎么变的。每出局一个人，其实就是把这个数组向前移动了M位。然后逆过来，就可以得到这个递推式。

因为求出的结果是数组中的下标，最终的编号还要加1

import java.util.*;
public class Main {
	public static void cir(int n,int m) {
		int p=0;
   //当n=1的时候 p还是0 不进入循环 直接输出即可
		for(int i=2;i<=n;i++) {
    //为何从2开始呢，因为开始只有1个人的时候不用计算，返回的位置肯定是0
    //所以循环要从2开始
			p=(p+m)%i;
		
		}
		System.out.println(p+1);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner reader =new Scanner(System.in);
		int n=reader.nextInt();
		int m=reader.nextInt();
		cir(n,m);
	}

}