第一次我的思路很清晰但超时，把数列输出来发现了规律，于是得出了第二种算法，却无法解释，复杂度由O(n)变为了O(logn)，结果ac
现把两次的思路写出来
（TLE）
a[1]=1;
for(i=2;i<=99000000;i++)
{
     a[i]=(a[i-1]+1)%i+1;
}

（AC）
当n=2^i(i=0,1,2...26)时 (2^26<99000000<2^27)也就是为2的幂时f(n)=1
当n为奇数时,f(n)=f(n/2)*2+1
当n不为2的幂且n为偶数时f(n)=f(n/2)*2-1

希望有大牛能够解释一下第二种算法的原理，最好再总结出一个公式并给出证明

• Re:第一次tle，第二次ac (5) zhenjie 2009-05-29 20:40:39
  • Re:第一次tle，第二次ac (58) analysiser 2009-07-25 14:40:44