求助(可能会剧透一些题解内容)
查看原帖
求助(可能会剧透一些题解内容)
184069
Imitators楼主2021/2/9 18:44

看完题解后蒟蒻对于循环节的合并有一点没太理解(几篇题解也没有详细讲述这个部分),希望大佬能帮忙看下思路哪里有问题,谢谢了!

我看了一下题解思路应该都是:把mm,分解质因数得到 m=∏piαim=\prod p_i^{\alpha_i},然后分别对每一个 pαp^\alpha 算出使 afn−1+bfn≡0(modpα)af_{n-1}+bf_{n}\equiv 0\pmod{p^\alpha} 最小的 nn。

由于斐波那契在  mod  p\bmod\ p 意义下存在循环节。

可以把每个关于 piαip_i^{\alpha_{i}} 的解 nin_i 列出如下的方程,求出最终解。

n≡n1(modl(p1α1))n\equiv n_1\pmod{l(p_1^{\alpha_1})} n≡n2(modl(p2α2))n\equiv n_2\pmod{l(p_2^{\alpha_2})} ⋮\vdots n≡nk(modl(pkαk))n\equiv n_k\pmod{l(p_k^{\alpha_k})}

到此,我有一个疑问,就是如果算每一个“小”方程的最小解的话,合并起来并不一定是最小解。

也就是可能存在 在  mod  p\bmod\ p 循环节内,有两个或者更多的相同解,此时取最小解合并后可能不是最小解。

那难道不是就决策不了该选哪一个解当作  mod p\bmod p 的解了吗?

2021/2/9 18:44
加载中...