首先考虑改变枚举顺序消去： 考虑刘维尔函数的定义，显然这个函数为完全积性函数且对于一个平方数，一定有，那么： 第三步是枚举时得出来的转变。现在只需要求解后一部分的。考虑的贝尔级数，不懂贝尔级数的读者可以到这篇文章进行学习。 这里的相当于： 逆推一下这个式子可以得到： 所以函数的意义是什么？由于两个积性函数的狄利克雷卷积仍是积性函数，那么当且仅当一个数的所有质因数的幂次可以被整除时，，否则。说明。此时原式等于： 时间复杂度 。

经典斐波那契套路题，首先你得知道斐波那契数列这样的一个性质。 有了这样一个性质，我们便可以把原式转为： 接下来就是经典的莫比乌斯反演套路了。但不太一样的是，我们需要在这一步打住： 令 ，由于 只有 的不同的取值情况且 可以通过数论分块 求解，根据大佬的结论，暴力求解 这样的函数所有取值情况时间复杂度貌似是 （反正跑得飞快）。现在只需要关注 的前缀和就行。还好这里还有个关于斐波那契数列前缀和 的公式： 这下将问题转移为单点求斐波那契数列的问题了。考虑 的通项公式： 因为 是模 的二次剩余，说明 在模 下存在意义。不会求二次剩余也不是很大问题，本地暴力求出即可，得到其中...