Colossal Fibonacci Numbers!

Colossal Fibonacci Numbers!

题意

给定a,b,c.求fib(a ^ b) % c

显然a ^ b 非常大，而且直接fib(a ^ b)是行不通的

解题背景

1. 我们首先知道（1 到 n) % m，在n足够的的时候会出现循环的。当对m取模的时候最大在 m*m之前会出现循环。
2. 我们知道(m + n) % mod == (m % mod + n % mod) % mod;
3. 所以可得fib[n] % mod = (fib[n - 1] % mod + fib[n - 2] % mod) % mod;

解题思路

1.首先在 1 ~ n * n 之间 算出 fib[i],在判断 fib[i] == fib[1] && fib[i - 1] == fib[0],如果符合条件。那 么i - 1 就是fib数列的周期。(为什么只要判断前两项就可以知道后面是重复的呢？？因为fib[i]只与前面的两项有关，那么前面两项确定以后，整个的后面就确定了).其中该fib数列的周期为 i - 1；

2.利用gcd(a % (i - 1),b,i - 1)算出a ^ b是在fib数列的第几项,（注意一定要mod一下，不然会 wa)。结果为fib[gcd(a % (i - 1),b,i - 1)]

3.注意特判一下 if(a == 0 || c == 1)res = 0;