首页 > 代码库 > 广义Fibonacci数列模n的循环节

广义Fibonacci数列模n的循环节

见这里:http://blog.csdn.net/ACdreamers/article/details/25616461 有详细的分析推理

只找出了循环节的上限,设 f[n] = (af[n - 1] + b[n - 2])%P,设序列a ={ f[1], f[2] }, 考虑t项后, b ={ f[t + 1], f[t + 2] }, 当t = p * p + 1时, 最多可以产生p * p + 1个不同的序列,其中至少会有一个与a相同, 而一旦与a相同,那么后面的项也会与a后面的项一样,所以循环节不会超过t - 1 = p * p

做题时假设循环节不会超过2 * (P + 1)就行了,如果暴力一分钟还没出解,那么~放弃吧~