2018徐州站网络赛D题 Easy Math

未分类

---

给定$n,m$,求$f(m,n)=\sum_{i=1}^m\mu(in)$.
数据范围:$1\le m \le 2e9,1\le n \le 1e12.$

如果$n$是有平方因子数也就是如果$\mu(n)=0$那么$f(m,n)=0$，结论显然.
如果$n$没有平方因子，那么：

$$\begin{align*} f(m,n) &= \sum_{i=1}^m\mu(in) \\ &= \sum_{i=1}^m\mu(i)\mu(n)*[gcd(i,n)==1]\\ &=\sum_{i=1}^m\mu(i)\mu(n)*\sum_{d|(i,n)}\mu(d) \\ &= \mu(n) \sum_{d|n}\mu(d) \sum_{i=1}^{\lfloor m/d \rfloor}\mu(i*d) \\ &= \mu(n)\sum_{d|n}\mu(d)f(\lfloor m/d \rfloor,d) \end{align*}$$

根据这个式子递归计算即可，注意有如下几个递归终止条件：
当$m=0,f(m,n)=0;$
当$m=1,f(m,n)=\mu(n);$
当$n=1,f(m,n)=\sum_{i=1}^m\mu(i).$这步需要使用杜教筛求莫比乌斯函数前$n$项和.
注意枚举$d$递归计算的时候，$\mu(d)$和$\mu(n)$的计算可以$O(1)$，只需要记录素数就可以直接计算了.以及由于$n$是无平方因子数，所以在给定的数据范围下，$n$最多有$11$个质因子，这时$n=2*3*5*7*11*13*17*19*23*29*31$，所以递归计算的复杂度会比较低.时间复杂度$O(能过)$

最后介绍一下用杜教筛求莫比乌斯函数前$n$项和.

$$f(n)=\sum_{i=1}^n\mu(i)$$
设$g(n)=1$，那么对$f,g$做狄利克雷卷积：
$$(f*g)(n)=\sum_{d|n}f(d)g(n/d)=\sum_{d|n}\mu(d)=[n==1]$$
那么：
$$\begin{align*} \sum_{i=1}^n (f*g)(i) &= \sum_{i=1}^n\sum_{d|i}f(d)g(i/d) \\ &= \sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor n/d \rfloor}f(i) \\ &= \sum_{d=1}^nf(\lfloor n/d \rfloor) \end{align*}$$
又因为$(f*g)(n)=[n==1]$，所以$\sum_{i=1}^n(f*g)(i)=1. (n\ge1)$
所以：
$$\sum_{d=1}^nf(\lfloor n/d \rfloor)=1$$
可以得到：
$$f(n)=1-\sum_{i=2}^nf(\lfloor n/i\rfloor)$$
用数论分块递归求解，线性筛预处理前$n^{2/3}$项的结果，可以做到$O(n^{2/3})$求解.

参考资料：莫比乌斯反演杜教筛：https://www.zybuluo.com/yang12138/note/1259539
$AC$代码：https://paste.ubuntu.com/p/VFtSpCS8Nd/