经典斐波那契套路题，首先你得知道斐波那契数列这样的一个性质。

有了这样一个性质，我们便可以把原式转为：

接下来就是经典的莫比乌斯反演套路了。但不太一样的是，我们需要在这一步打住：

令 ，由于 只有 的不同的取值情况且 可以通过数论分块 求解，根据大佬的结论，暴力求解 这样的函数所有取值情况时间复杂度貌似是 （反正跑得飞快）。现在只需要关注 的前缀和就行。还好这里还有个关于斐波那契数列前缀和 的公式：

这下将问题转移为单点求斐波那契数列的问题了。考虑 的通项公式：

因为 是模 的二次剩余，说明 在模 下存在意义。不会求二次剩余也不是很大问题，本地暴力求出即可，得到其中一个解为 ，即可以用 替换原式中的 ，那么此时原式就可以进行数论分块了。总的复杂度为 。