胡扯min_25筛

记质数集合为P

Problem

以低于线性的复杂度求一类积性函数的和,函数需满足
f(p),f(p^k)(p\in P)很好求。

Solution

{\rm Min}(x)x的最小质因子。

g

g(n,i)=\sum f(x)[ {x\le n {\ \rm and\ } (x \in P {\ \rm or\ } {\rm Min}(x)>P_i) } ]
n < P_i^2时,g(n,i)=g(n,i-1),因为最小的{\rm Min}(x)= P_i的合数就是P_i^2
否则,考虑从g(n,i-1)中减去{\rm Min}(x)= P_i的合数的贡献,也就是\sum f(x)[{x\le n,{\rm Min}(x)=P_i}],提出f(P_i),式子变成了f(P_i)(g([\frac n{P_i}],i-1)-\sum_{j=1}^{i-1}f(P_j))
\therefore
g(n,i)= \begin{cases} g(n,i-1)&,n < P_i^2\\ g(n,i-1)-f(P_i)(g([\frac n{P_i}],i-1)-\sum_{j=1}^{i-1}f(P_j))&,\text{otherwise} \end{cases}

h

h(n,i)=\sum_{j=1}^nf(j)[{\rm Min}(j)\ge P_i]
对于h(n,i)n以内质数的贡献是g(n,|P|)-\sum_{j=1}^{i-1}f(P_j)
现在考虑合数的贡献。
枚举合数的最小质因子P_j,那么最小质因子为P_j的合数的贡献就是\sum_{t\ge 1,P_j^{t+1}\le n}(h([\frac n{P_j^t}],j+1)f(P_j^t)+f(P_j^{t+1}))
因此
h(n,i)=g(n,|P|)-\sum_{j=1}^{i-1}f(P_j)+\sum_{j\ge i}\sum_{t\ge 1,P_j^{t+1}\le n}(h([\frac n{P_j^t}],j+1)f(P_j^t)+f(P_j^{t+1}))
答案就是h(n,1)了。

Tips

具体实现的时候,g不一定求\sum f(x)[ {x\le n {\ \rm and\ } (x \in P {\ \rm or\ } {\rm Min}(x)>P_i) } ],求出的g只要能使得上式可以被很快求出即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注