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

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

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

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

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

nn1(modl(p1α1))n\equiv n_1\pmod{l(p_1^{\alpha_1})} nn2(modl(p2α2))n\equiv n_2\pmod{l(p_2^{\alpha_2})} \vdots nnk(modl(pkαk))n\equiv n_k\pmod{l(p_k^{\alpha_k})}

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

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

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

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