本文主要是介绍Colossal Fibonacci Numbers!,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意
给定a,b,c.求fib(a ^ b) % c
显然a ^ b 非常大,而且直接fib(a ^ b)是行不通的
解题背景
- 我们首先知道(1 到 n) % m,在n足够的的时候会出现循环的。当对m取模的时候最大在 m*m之前会出现循环。
- 我们知道(m + n) % mod == (m % mod + n % mod) % mod;
- 所以可得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;
这篇关于Colossal Fibonacci Numbers!的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!