[求助][讨论]ZJU2072近似线性是算法也TLE了

http://acm.zju.edu.cn/show_problem.php?pid=2072
感觉可能存在O(1)的算法，那就是一个公式问题了，程序爱好者们一起想想
为了不影响大家的思路，我的代码和分析就先不贴出来了

看了一会，就不知道那个函数J(n)是怎么计算的，最后个生还者产生没规律？

指教指教！

J(n)代表每个人持有密码2的约瑟夫环问题的解

//zju 2072 why time limit exceeded?

//#include"stdafx.h"
#include<iostream>
using namespace std;

int main()
{
long long M, N, i;
while(cin >> M >> N)
{
for(i = 0; i < N; i++)
{
M /= 2;
M++;
}
cout << M - 1 << endl;
}
return 0;
}

回复：（leeco）[求助][讨论]ZJU2072近似线性是算法也...

/*---------------------------------------------------------------------------
File name: ZJU2072-Recursive Survival-reply-leeco.c
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 8/3/2007 18:46:06
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Reply to leeco's post at
http://bbs.bc-cn.net/viewthread.php?tid=140015

#2 --- I am sorry that I did not make it #1. You may optimize the code
and make it #1 there.

2 2007-08-04 09:37:35 00:00.00 392K C HJin
*/

#define i64 long long

/** compute J(n)

O(lg(n)) (<=63 for this problem) since I need to find how many
binary bits n has.

Note tha 2^p-1 (p=1, 2, 3, ...) are fixed points of J; i.e.,
J(n) = n if and only if n=2^p-1.

I would think you can save a lot of time by using assembly
code for shifting and rotating.
*/
i64 J(i64 n)
{
int k=0;
i64 t=n;
while(t)
{
++k;
t>>=1;
}

t=n;
t^=(1ll<<(k-1));
t<<=1;
t|=1;

return t;
}

main()
{
i64 n, k, t;
int i;

while(scanf("%lld%lld", &n, &k)!=-1)
{
/** compute J(J(...J(n))).
It repeats no more than 63 times.

For each input pair (n, k), it will take around
O(63^2) time.
*/
for(i=1; i<=k; ++i)
{
if(n==1ll)
break;
t=J(n);
if(n==t)
break;
n=t;
}

printf("%lld\n", n);
}
}

I can get it.
Thanks !!