找规律

约瑟夫环问题变形。

在这个约瑟夫环问题中，固定每次间隔两人，10个人，杀人顺序为2,4,6,8,10,3,7，1,9，最后剩下5

定义一种运算J^m(n) 表示 m次嵌套 J(  J( J(n) )

好像J^2(10) = J(J(10)) = J(5) = 3

而m和n的最大值是 10^9

这个问题 主要是能快速算出 J（n），不难想到如果能算出J（n），可以暴力地一步一步迭代下去做m次，容容易发现不用做m次，因为J(1) = 1，当n降到1的时候，m再大都没意义了

可以发现这个问题是指数递减的，m<=10^9 是个纸老虎

 

同样地可以打表看看J（n）的值，一看就能看到规律

对于一个范围的n  ，  [  2^k , 2^(k+1)  ）  （左闭右开区间）

可以发现里面的J（n） 依次为  1,3,5,7,9,11 …………2^(k+1) -1 

这样就得到了公式  J(n) = 1+（n - 2^k）*2   要求  2^k <= n < 2^(k+1)

所以我们可以先保存所有的2^k，当然得到n的时候在找2^k也是可以的

 

用上面的公式，不断地算J(n)，算m次即可，过程中如果n=1，那么就可以跳出不用再算了

 

#include 
     
      #include 
      
       typedef long long ll;ll tk[50+10];void init_tk(){    tk[0]=1;    for(int i=1; i<=40; i++)        tk[i] = tk[i-1] * 2;//    for(int i=0; i<=40; i++)//        printf("%I64d\n",tk[i]);}int search(ll n){    for(int i=0; i<=40; i++)        if(tk[i] <= n && tk[i+1] > n)            return i;    return -1;}int main(){    init_tk();    ll n,m;    while(scanf("%lld%lld",&n,&m)!=EOF)    {        if(!n && !m) break;        while(n>1 && m)        {            int b = search(n);            ll ans = 1 + (n - tk[b])*2;            n = ans;            m--;        }        printf("%lld\n",n);    }    return 0;}