51Nod1355 斐波那契的最小公倍数

题意：给出 ，求 其中 是斐波那契数列。

，，结果对 取模。

---

• 结论：。

  证明：

  • 引理 1：。

    证明：，归纳即证。

  • 引理 2：。

    证明：构造斐波那契数列的转移矩阵，考虑从向量 转移 次来到 ，即证。

  根据欧几里得算法（辗转相减），只需证明 。

• 推广：对于

---

我们已经会求解 了，现在考虑如何求解 。

对于集合 ：

• 取每个素数的指数最大值
• 取每个素数的指数最小值

这让我们联想到 Min_Max 容斥： 记 考虑指数同样可以得到： 对于多个质数的情况，不难得到同样的结论： 故 按这个式子爆算是 的，无法承受。

---

注意到出题人很良心地给了 ，考虑在这上面做手脚。

考虑分别对每个 记录贡献幂次，最后分别乘上，只需考虑 ，所以可做。

设 则答案为

---

下面考虑 如何求出。

运用莫比乌斯反演，记：

• ，即计数。
• 为 中 的倍数的集合。
• 。

令 容易 求出 ，然后得到 ，反演得 总复杂度 。（快速幂也是 ）