对于给定的 n 和 m 值，求 fib(n) mod m 其中 n 非常大。 （皮萨诺时期）
For a given value of n and m, find fib(n) mod m where n is very huge. (Pisano Period)
输入
整数 'n'（最多 10^14）和 'm'（最多 10^3）
输出
Fib(n) modulo m
样本案例
输入：239 1000 输出：161
输入：2816213588 239 输出：151
问题中给出的提示
由于不可能迭代'n'次（因为n很大），考虑使用皮萨诺周期（当每个元素斐波那契数列除以任何整数时重复余数）
我写的代码（可能是错误的，但通过了上述情况）
n, m = map(int, input().split())
a, b = 0, 1
fib_rems = [0, 1] # remainders after diving 'm'
fib = [0, 1] # regular fibonacci series
while True:
a, b = b, a+b # cotinuing to grow Fibonacci series
fib.append(b)
fib_rems.append(b%m)
# checking if last two items in remainder are 0, 1 which is indication to pisano period
if fib_rems[-2] == 0 and fib_rems[-1] == 1:
# remving last two items in fib and fib_rems which are 1 and 0 so we get length equivalet excatly one period
fib_rems.pop()
fib_rems.pop()
fib.pop()
fib.pop()
break
period = len(fib_rems)
rem = n % period
print(fib[rem]%m)
我做的第一件事是找出皮萨诺周期（余数重复的长度）并且对其余部分感到困惑。
- 为什么 fib(n=2015) mod 3 等同于 fib(7) mod 3？ （对于 = 3，周期为 01120221，长度为 8，2015=251*8 + 7）
- 一般得到余数序列后，如何（数学证明）计算Fib(n)mod m?
- 我可以improve/optimize上面的代码吗？
（总之上面最后两行代码我没看懂）
任何 hints/guidance/reference/solution 不胜感激！
您可以使用二进制取幂使其更快。
最终归结为以下两个二次递归关系：
F(2 n -1) = F( n)^2 + F(n -1)^2
F(2 n) = (2 F( n -1) + F(n)) F(n)
您可以在每一步取余数模 m。
每个数字都可以表示为ax + b
对于 n=2015 和 m=3
2015 = (no_of_times_period_repeated)*(length_of_period) + 剩余
0 =< 剩菜 <= length_of_period
剩余的值是 fib(n) 的余数在 values_in_period 数组中的索引。
2015 = 251*8 + 7
另外，2015 % len(period) = 7
values_in_period = [0, 1, 1, 2, 0, 2, 2, 1]
在这种情况下，由于我们剩下的是 7（即 fib(n) 的余数所在的索引），所以 values_in_period 的第 7 个索引是 1 是我们的答案！
fib(2015) mod 3 可以简化为 fib(7) mod 3 因为斐波那契数列中每第 7 个值的余数相同，所以 fib(7) mod 为了简单起见，可以考虑3，但它不是必需的，完全脱离了上下文。
输入
整数 'n'（最多 10^14）和 'm'（最多 10^3）
输出
Fib(n) modulo m
样本案例
输入：239 1000 输出：161 输入：2816213588 239 输出：151
问题中给出的提示
由于不可能迭代'n'次（因为n很大），考虑使用皮萨诺周期（当每个元素斐波那契数列除以任何整数时重复余数）
我写的代码（可能是错误的，但通过了上述情况）
n, m = map(int, input().split())
a, b = 0, 1
fib_rems = [0, 1] # remainders after diving 'm'
fib = [0, 1] # regular fibonacci series
while True:
a, b = b, a+b # cotinuing to grow Fibonacci series
fib.append(b)
fib_rems.append(b%m)
# checking if last two items in remainder are 0, 1 which is indication to pisano period
if fib_rems[-2] == 0 and fib_rems[-1] == 1:
# remving last two items in fib and fib_rems which are 1 and 0 so we get length equivalet excatly one period
fib_rems.pop()
fib_rems.pop()
fib.pop()
fib.pop()
break
period = len(fib_rems)
rem = n % period
print(fib[rem]%m)
我做的第一件事是找出皮萨诺周期（余数重复的长度）并且对其余部分感到困惑。
- 为什么 fib(n=2015) mod 3 等同于 fib(7) mod 3？ （对于 = 3，周期为 01120221，长度为 8，2015=251*8 + 7）
- 一般得到余数序列后，如何（数学证明）计算Fib(n)mod m?
- 我可以improve/optimize上面的代码吗？
（总之上面最后两行代码我没看懂）
任何 hints/guidance/reference/solution 不胜感激！
您可以使用二进制取幂使其更快。 最终归结为以下两个二次递归关系：
F(2 n -1) = F( n)^2 + F(n -1)^2
F(2 n) = (2 F( n -1) + F(n)) F(n)
您可以在每一步取余数模 m。
每个数字都可以表示为ax + b
对于 n=2015 和 m=3
2015 = (no_of_times_period_repeated)*(length_of_period) + 剩余
0 =< 剩菜 <= length_of_period
剩余的值是 fib(n) 的余数在 values_in_period 数组中的索引。
2015 = 251*8 + 7
另外，2015 % len(period) = 7
values_in_period = [0, 1, 1, 2, 0, 2, 2, 1]
在这种情况下，由于我们剩下的是 7（即 fib(n) 的余数所在的索引），所以 values_in_period 的第 7 个索引是 1 是我们的答案！
fib(2015) mod 3 可以简化为 fib(7) mod 3 因为斐波那契数列中每第 7 个值的余数相同，所以 fib(7) mod 为了简单起见，可以考虑3，但它不是必需的，完全脱离了上下文。