看完题解后蒟蒻对于循环节的合并有一点没太理解(几篇题解也没有详细讲述这个部分),希望大佬能帮忙看下思路哪里有问题,谢谢了!
我看了一下题解思路应该都是:把m,分解质因数得到 m=∏piαi,然后分别对每一个 pα 算出使 afn−1+bfn≡0(modpα) 最小的 n。
由于斐波那契在 mod p 意义下存在循环节。
可以把每个关于 piαi 的解 ni 列出如下的方程,求出最终解。
n≡n1(modl(p1α1))
n≡n2(modl(p2α2))
⋮
n≡nk(modl(pkαk))
到此,我有一个疑问,就是如果算每一个“小”方程的最小解的话,合并起来并不一定是最小解。
也就是可能存在 在 mod p 循环节内,有两个或者更多的相同解,此时取最小解合并后可能不是最小解。
那难道不是就决策不了该选哪一个解当作 modp 的解了吗?