2014
03-01

# Josephus again

In our Jesephus game, we start with n people numbered 1 to n around a circle, and we eliminated every k remaining person until only one survives. For example, here’s the starting configuration for n = 10, k = 2, The elimination order is 2, 4, 6, 8, 10, 3, 7, 1, 9. So 5 survives.The problem: determine the survivor’s number , J(n, k).

There are multiple cases, end with EOF
each case have two integer, n, k. (1<= n <= 10^12, 1 <= k <= 1000)

There are multiple cases, end with EOF
each case have two integer, n, k. (1<= n <= 10^12, 1 <= k <= 1000)

10 2
10 3

5
4

num+x*m < i+(x-1) //注意后面是x-1,因为每次都是当num增加完后才增加i的，可以用小数据模拟一下就清楚了

x < (i-num)/(m-1)

num += x*m

i += x

//约瑟夫循环问题
//编号从0开始
//假设n = 4, m = 2, k = 1
//第一个出队的人的编号是3
LL josephus(LL n, LL m, LL k)//分别为：人数，出圈步长，起使报数位置
{
LL num = 0;
if(m == 1)
{
return (n-1+k)%n;
}
for(LL i = 2; i <= n;)
if((num+m) < i)
{
LL temp = (i-1-num)%(m-1)? (i-1-num)/(m-1): (i-1-num)/(m-1)-1;
if(i+temp > n)   //当i+temp > n时特判
{
num += (n+1-i)*m;    //直接得到最终解
break;
}
num += temp*m;
i += temp;
}
else
{
num = (num+m)%i;  //普通递推
++i;
}
num = (num+k)%n;
return num;
}

1. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？

2. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。