题意
给定\(n,m\),求\(\sum\limits_{i=1}^m \mu(in)\)
\(m\le 10^9,n\le 10^{12}\)
做法一
\(\sum\limits_{i=1}^m \mu(i,n)=\mu(n)\sum\limits_{i=1}^m \mu(i)[(i,n)=1]\)
\(f(i)=\mu(i)[(i,n)=1]\)是关于\(i\)的积性函数,考虑用min25筛
令\(S(N,t)=\sum\limits_{i=1}^N f(i)[min(i)\ge prime_t]\)
那么\(S(N,t)=T+\sum\limits_{i=t} [prime_i\nmid n]S(N/prime_i,i+1)\),其中\(T=\sum\limits_{i=t} [prime_i\le N][prime_i\nmid n]\)
由于这里的这和我们平时写的min25筛简化了很多,所以跑起来非常快
做法二
这是std的做法
令\(F(m,n)=\sum\limits_{i=1}^m \mu(i,n)\),令\(p\)为\(n\)的最小质因子
\[\begin{aligned} F(m,n)&=\sum\limits_{i=1}^m \mu(i,n)\\ &=\sum\limits_{p|i} \mu(in)+\sum\limits_{p\nmid i}\mu(in)\\ &=\sum\limits_{p\nmid i}\mu(i\cdot n/p\cdot p)\\ &=-\sum\limits_{p\nmid i}\mu(i\cdots n/p)\\ &=-(\sum\limits_{i=1}^m \mu(i\cdot n/p)-\sum\limits_{i=1}^{m/p}\mu(i\cdot p\cdot n/p))\\ &=-(F(m,n/p)-F(m/p,n)) \end{aligned}\]边界情况:\(F(0,N)=0\);\(F(N,1)\)是求莫比乌斯函数的前缀和,用杜教筛计算
\(F(m,n)\)第一维状态数是\(O(\sqrt{m})\)的第二位状态数是\(O(n的质因子个数)\)