ROSECODE 240

广义皮萨诺周期 2

Generalized Pisano Period 2

Min_25 · 数学 · 2015-05-07

令 $F_{k} (n)$ 为线性递归序列，使得 $\begin{aligned} F_{k} (n) & = 1 (1 \leq n \leq k), \\ F_{k} (n) & = \sum_{i = 1}^{k} F_{k} (n - i) (n > k) . \end{aligned}$

例如， $F_{2} (1) = 1$ 、 $F_{2} (2) = 1$ 和 $F_{2} (3) = 2$

令 $P (k, m)$ 为 $F_{k} (n)$ 模 $m$ 的（最小）周期。

给您 $P (2, 10) = 60$ 和 $P (2, 10^{9}) = 1 500 000 000$ 。

找到 $P (50, 10^{9})$ 。

注意：答案是 29 位数字。

[我的计时：42 秒（PyPy）]