被迫营业。应用范围：求\(\sum_{i=1}^nf(i)\)，其中\(f(i)\)是积性函数。需要满足\(f(i)\)在\(i\)是质数时的取值是多项式。时间复杂度：\(\Theta(n^{1-\epsilon})\)/\(\Theta(\frac{n^{\frac{3}{4}}}{\logn})\)。主要想法是将\(f(i)\)分成三个部分后求和：\(i\)是质数，\(

习题部分:#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10,mod=1e9+7;typedeflonglongll;lln,sq;llv[N],prime[N],sp1[N],sp2[N],cnt;llg1[N],g2[N],w[N],id1[N],id2[N],tot;llqkp(lla,llb){ llans=1; for(;b;b>>=

min25筛可以处理这样一类问题：求$F(x)$的前缀和，其中$F(x)$是积性函数，且可以表示成$F(p)=p^a+p^b+...$这样的形式，其中$p$是质数。如果$F(p)$是多项式，我们把它们拆开分别算，然后加起来。我们希望先求出其质数位置上的值，设$g(i,j)$为$[2,i]$中，删去了$p_1$到

之前学习的的确是太浅薄了，于是重新学习一下。可以做什么？对于满足条件的积性函数\(f(n)\)，求其前\(n\)项和\(\sum_{i=1}^nf(i)\)。需要准备些什么？设\(N=\{x|x=\lfloor\frac{n}{i}\rfloor\}\)，即为所有整除的不同点值。设\(B=\sqrtn,p_{k}\)代表\(\leB\)的所有质

前置知识：min25筛，即你要用min25筛通过板子题，不管写成啥样，不管常数多大，但是你要了解一点min25。没有特殊说明的话有如下记号（大部分记号与oi-wiki一致）：\(x/y=\lfloor\frac{x}{y}\rfloor\)\(\text{P}\)为素数集合，\(p_k\)表示第\(k\)小素数。特别地，令\(p_{0}=1\)。\(\t

min25筛min25筛用于求一类数论函数的前缀和，适用于函数在素数处的取值可以用一个关于此素数的多项式来表示的数论函数。处理质数部分这部分我们需要解决\(\sum\limits_{p\subseteqprime}f(p)\)，这里简单起见，假设\(f(p)=p^t\)用\(s_i\)表示前\(i\)个质数之和，用\(LPF_i\)表示\(i

时间复杂度为解决的问题有：用来求积性函数前缀和，要求有是一个关于质数p的项数较小的多项式或者能快速求值可以快速求值前置知识：积性函数:对于互质的整数和有性质完全积性函数：对于任意整数和有性质规定是从小到大第零个质数，是从小到大第一个质数在以内没有任何一个合数的最小质因子

发现这个东西很容易忘，果然还是理解不够吧，写一篇博客方便以后复习。杜教筛目的是要求\(S(n)=\sum_{i=1}^nf(i)\)。我们需要构造两个函数\(g,h\)满足\(f*g=h\)，其中\(h\)是一个积性函数且能快速求和。考虑求\(\sum_{i=1}^n\sum_{d|i}f(d)g(\dfrac{i}{d})=\sum_{i=1}

博客两年没更了，其实博主有在打ACM，但是因为平时用Latex而不是Markdown所以就算写了点东西也懒得搬，最近准备搬点知识点总结过来用途求积性函数\(f\)的前缀和\(F(

#6053.简单的函数先求g(n,j)目的是为了在求S(n,j)的时候可以快速获取一些质数上的点的值。所以我们只要求g(n,j)的质数处的值正确即可其他值则不需要所以我们可以让g

本题是2022CCPCF题的强化版.给出一个n,m求出所有长度小于等于n的数列\(a_k(k\len)\)且\(a_k\lem\)且\(a_i|a_{i+1}\)固定n显然可以发现对于m的标准分解\(m=p_1^{k

一些记号：记\(\mathbb{P}\)为质数集，\(p_i\)表示第\(i\)个质数。记\(\operatorname{lpf}(x)\)表示\(x\)的最小质因数为第几个质数。特别地，令\(\operatorname{l