0001 class Fib { //Fibonacci数列类
0002 private:
0003    uint64_t f, g; //f = fib(k-1), g = fib(k)
0004 public:
0005    Fib(Rank n) //初始化为不小于n的最小Fibonacci项
0006    { f = 1;  g = 0;  while (g < n) next(); } //fib(-1), fib(0)，O(log_phi(n))时间
0007    uint64_t get()  { return g; } //获取当前Fibonacci项，O(1)时间
0008    uint64_t next() { g += f;  f = g-f;  return g; } //转至下一Fibonacci项，O(1)时间
0009    uint64_t prev() { f = g-f;  g -= f;  return g; } //转至上一Fibonacci项，O(1)时间
0010 };