题目传送门
题目大意是给定一个广义 Fibonacci 数列 ，其中 ，求有多少 在 范围内，满足 。
首先 的范围很大，考虑模意义下的广义 Fibonacci 数列的循环节长度大概是 的， 是模数，因此我们先把循环节求出来。
求广义 Fibonacci 数列循环节在这篇文章给出了详细证明过程，在本题的结论是：
- 若 是模 的二次剩余，则最小循环节长度是 的一个因子；
- 若 不是模 的二次剩余，则最小循环节长度是 的一个因子；
- 若 ，则最小循环节长度为 。
最后一条结论不会证明，但是跑了 以内的满足条件的数应该都是满足的。
所以套用 Pollard Rho 即可进行快速的因数枚举，之后使用矩阵快速幂判断是否是循环节即可，复杂度是 ， 指的是 的因数个数。
现在我们把整个序列的范围缩小到了一个 长度的循环节内，下面考虑一个循环节内模 为 的位置怎么求。考虑一个经典题是给两个数，问在广义 Fibonacci 数列出现的位置，这个是用这两个数构造矩阵，用 BSGS 求即可。这里只出现了一个数，没办法构造矩阵的。
考虑 Cassini's identity，有 。这里按照行列式证明的方式，易知本题中这个性质仍然满足。因此设 ，则方程
成立。
因为我们要求出 才能根据 和 求出 ，但所有满足条件的解一定满足方程，所以我们先讨论奇偶，然后发现这个是一个模意义下解二次方程。利用求根公式求，如果根号下的数在模 意义下不存在二次剩余，则忽略它，因为要求的是实根，否则找个二次剩余板子把解求出来，然后套用上面提到的 BSGS 把位置求出来。
根据方程性质，可以知道在一个循环节内最多有 个解，然后就套用 BSGS 求位置，根据循环节长度算算即可。
然后就会收到一个大大的 TLE。
仔细分析，因为我们求解的是一个矩阵 ，其中：
是我们构造的矩阵。按照正常的矩阵求解，是拆成 而非 的形式以避免矩阵求逆，但是拆成 的话第一步小步的值需要求四次，而拆成 的话小步的结果就可以保留下来，大步中还能复用。所幸 是可逆的，因此根据这个性质，就从原来的最大 的 BSGS 过程变成了 ，就能卡过去了。
时间复杂度：，空间复杂度：。
代码在这里