题解 P7325
前言
数学符号约定
- \(a,b,p\)：表示任意自然数。
- \(F_x\)：表示广义斐波那契数列的第 \(x\) 项。
- \(f_x\)：表示普通斐波那契数列的第 \(x\) 项.
如非特殊说明，将会按照上述约定书写符号。
题目分析
首先引入一条定理：
普通斐波那契数列在模 \(m\) 意义下纯循环，且循环节为 \(O(m)\)。
证明可以去看 wlzhouzhuan 的博客，碍于篇幅限制不多赘述。
然后我们定义 \(F_0 = a,\, F_1 = b\)，则显然我们有：\(F_p = af_{p-1} + bf_{p}\)，证明平凡，如果想不出来可以手玩一下试试。
此时，我们的目标是对于 \(a,b\) 求出 \(p\) 使其满足下式：
\[af_{p-1} + bf_p \equiv 0 \pmod {m}
\]
移项，得：
\[af_{p-1} \equiv -bf_p \pmod m
\]
此时，我们不妨令 \(t = -b\)，则我们有：
\[af_{p-1} \equiv tf_p \pmod m
\]
观察上式，发现如果我们能将 \(f_{p-1}\) 和 \(t\) 分别移项，然后预处理 \(\dfrac {f_p}{f_{p-1}}\) 问题就十分的简单了，但是因为 \(m\) 不为质数，故我们不能这么做。
然而，俗话说的好，没有条件就让我们创造条件，先考虑 \(t\) 的移项，设 \(d = \gcd(a,t,m)\)，则