fibo 수구법 - 저자 소택

fibonacci 수의 귀속 구법:

 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 }