Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Fibonacci O(log n) 非矩阵算法

Posted by flyinghearts at 2010-09-04 22:52:06 on Problem 3070
详细说明见:http://www.cppblog.com/flyinghearts/archive/2010/08/02/118593.html

算法:
  F(n+2) = F(n+1) + F(n)  
   用归纳法可证明:F(n) = F(k)*F(n+1-k) + F(k-1)*F(n-k)
  利用这两个公式可实现O(log n)。

unsigned fib_last4( unsigned num)
{
  if ( num == 0 ) return 0;
  const unsigned M=10000;
  unsigned ret=1,next=1,ret_=ret;
  unsigned flag=1, tt=num;
  while ( tt >>= 1) flag <<= 1;
  while ( flag >>= 1 ){
    if ( num & flag ){
      ret_ = ret * ret + next * next;
      next = (ret + ret + next) * next;
    } else {
      //多加一个M,避免 2*next-ret是负数,造成结果不对
      ret_ = (next + next + M - ret) * ret;
      next = ret * ret + next * next;
    }
    ret = ret_ % M;
    next = next % M;
  }
  return ret;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator