fibo数求法(递归版本) -- 作者小泽

 1  
 2 struct Fib
 3 {
 4     int x1;
 5     int x2;
 6 };
 7 
 8 Fib fib(int x)
 9 {
10     Fib ans;
11     if(x == 2)
12     {
13         ans.x1 = 0;
14         ans.x2 = 1%MOD;
15         return ans;
16     }
17     Fib temp;
18     int x1 = x/2, x2 = x1 - 1;
19     if(x1%2)
20     {
21         temp = fib(x2);
22         ans.x1 = (2*temp.x1 + temp.x2)*temp.x2%MOD;
23         ans.x2 = ((temp.x1 + temp.x2)*(temp.x1 + temp.x2) + temp.x2*temp.x2)%MOD;
24     }
25     else
26     {
27         temp = fib(x1);
28         ans.x1 = (temp.x1*temp.x1 + temp.x2*temp.x2)%MOD;
29         ans.x2 = (2*temp.x1 + temp.x2)*temp.x2%MOD;
30     }
31     return ans;
32 }