莫比乌斯反演学习笔记

莫比乌斯反演是一种数论中用于计数的算法。

看上去挺难的，实际上挺简单的。

积性函数

感觉要写的东西有点多，所以还是分开单独写一篇吧。

莫比乌斯反演的基本原理就是。

也就是说，如果我们在一个式子中看到了，我们就可以将他转化为。

题意：求。其中。 $枚举是多少和一定是倍数，枚举的定义莫比乌斯反演把提前枚举狄利克雷卷积的定义$

暴力计算，时间复杂度为，可以通过。

我最后一步是用数论分块做的，时间复杂度不变。

改为杜教筛复杂度可以变为。

题意：组询问，每次给出，求出：所有数字。

显然，我们可以使用前缀和大法，所以我们只需要求：我们假设（不满足就交换一下），然后来颓柿子：直接计算时间复杂度，无法通过。

数论分块即可，时间复杂度。

题意：求。其中。

时限，空限。分子和分母我们可以分开算。

分子比较简单：分母：暴力这样做是的，应该可以通过。

我在做的时候对上面的式子进行整除分块，时间复杂度为：

这道题就有点难度了。

求。

共组数据。

最大点时限。

还是一样，先颓柿子。前面两个总时间复杂度是，所以我们需要快速计算后面的括号。

不难发现，这是一个等比数列的和。

我们可以在时间内求出等比数列，就像这个样子：这需要两次快速幂，常数比较大，我们可以进行优化。 $为奇数$ 可以递推，也可以递推。

时间复杂度。

后面还有两道需要杜教筛的题。