\rm Min25笔记

(类)积性函数前缀和:\sum_{i\geq 1}^nF(i)

P为质数集合,P_i是第i个质数

考虑把前缀和拆分为质数和合数讨论:

\sum_{i\geq 1}^nF(i)=\sum_{i\in P,i\leq n}F(i)+\sum_{i\notin P,i\leq n}F(i)

暂且不考虑上述式子的做法,引入一个新的函数g(n,j)=\sum_{i\geq 1}[i\in P]\or[\min\{p,p|i\}>P_j]\times f(j),然后考虑g(n,j)g(n,j-1)的转移

  1. P_j^2>n ,则P_j作为最小质因子时没有贡献

  2. P_{j}^2 \leq n,则g(n,j-1)-g(n,j)=D(j)D(j)=\sum_{i\geq 1}[i \notin P]\and[\min\{p,p|i\}=P_j]\times f(i)

    考虑D(j)怎么用g表示,显然对于所有有贡献的i有至少一个一个P_j质因子,并且在除去P_j后最小质因子依然\geq P_j(或者说>P_{j-1}),提取P_j之后所有数应该\geq P_j,因此包含了这部分的系数为g(\frac{n}{P_j},j-1),这其中包含了(1,\frac{n}{P_j}]的质数,按照上述要素划分为两部分,(1,P_j]\cup(P_j,\lfloor \frac{n}{P_j}\rfloor),前面部分的质数不应该存在,因此应减去g(P_j-1,j-1)

综上

g(n,j)=g(n,j-1)-f(P_j)\times\left(g\left(\frac{n}{P_j},j -1\right)-g(P_j-1,j-1)\right)

容易注意到g(P_j-1,j-1)=\sum_{i\geq 2}^{P_{j-1}}f(i),且P_j^2\leq n\Rightarrow P_j\leq \sqrt{n},对于前面一项就是\leq O(\sqrt{n})\sum_{i\in P, i\leq \sqrt{n}}F(i),可以线性筛;而1 . . .n中所有质数的F和为g(n,x),其中x是最后一个\leq \sqrt{n}的质数

回到质数和合数的分类讨论上来,质数较好计算,对于合数,可以考虑枚举他的最小质因子p和最小值因子的次数,因为上述讨论时发现\forall j, P_j \leq \sqrt{n},因此纳入了线性可计算的范围之内:

\sum_{i\notin P, i\leq n}F(i)=\sum_{i\geq 1}\sum_{e\geq 1,P_i^n}f(P_{i}^e)\left(\sum_{1\leq j\leq n/P_i^e, \min\{x\in P,x|j\} > p }f(j)\right)

sp_j=\sum_{i\geq 1}^{j}F(P_i)=g(j,x), S(n,t)表示1 ...n中最小质因子大于P_t的函数值之和,答案即为S(n,0)

S(n,t)=g(n,x)-sp_t+\sum_{p_{k}^e\leq n,k>t}f(p_k^e)\left(S\left(\frac{n}{p_k^e},k\right)+[e\neq 1]\right)

其中t设为P_t \leq \sqrt{n}且最大的P_t

前半部分表示>P_t的质数的答案(因为g(n,x)中包含了\leq n的质数),另一部分是最小质因子大于P_t的合数答案

要点:

  1. 因为是积性函数,所以要求f(A)f(B)=f(AB)\gcd(A,B)=1,因此分点计算P_j,计算含有P_t且除去P_t^e之后不含P_t的质因子,因此互质
  2. 因为除去了最小质因子,因此转化为了最小质因子>P_t的计数,同时质数和合数分离
  3. 考虑二元限制:枚举上限和合数最小质因子\Rightarrow构造出g(n,x)

Min25 积性函数 数论 筛法

2022.10.15补
上一篇 «
2022.10.11补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors