杂题

题意

给定\(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的质因子个数)\)

上一篇:视觉SLAM十四讲从理论到实践|2-eigen|visualizeGeometry


下一篇:渗透中POC、EXP、Payload与Shellcode的区别