min25筛
min25筛是什么
min25筛是一种筛法，他能以亚线性的时间复杂度筛出一类函数的前缀和
定义一部分符号
\(M(x) x\gt1\)代表\(x\)的最小质因子
我们再设\(P_j\)为第\(j\)小的质数, \(P_1=2,P_2=3,P_3=5...\)
先看最简单的第一类函数
\[ \begin{aligned} f(x)=\left\{\begin{matrix} x^k&x\in primes\\ 0&x \notin primes \end{matrix}\right. \end{aligned} \] 对于这个函数我们可以利用min25筛来达到\(O(\frac{n^\frac{3}{4}}{lg(n)})\)的时间复杂度，我们没有办法直接求这个函数的前缀和，但是我们可以另外设一个相对好求的函数\(h(x)=x^k\)，通过h来求f，因为\(\begin{aligned}\sum_{i=2}^nh(i)[i\in primes]=\sum_{i=2}^nf(i)[i\in primes]\end{aligned}\)
设\(\begin{aligned} g(n,j)=\sum_{i=2}^nh(i)[i \in primes或M(i)\gt P_j] \end{aligned}\)
即 i要么是质数，要么i的最小质因子大于\(P_j\)。对g函数的理解，我们甚至可以回忆埃式筛,每一轮都会选择一个最小的质数，然后筛掉他的所有倍数，最终唯有所有的质数不会被筛掉，我们的这个函数就是那些没有被筛掉的数的函数值的和。
\[
\begin{aligned}
g(n,j)=\left\{\begin{matrix}
g(n,j-1)-x&M(n)\le P_j\\
g(n,j-1)& M(n)\gt P_j
\end{matrix}\right.
\end{aligned}
\] x处是什么呢?第j-1次的结果和第j次的结果有什么不同呢？第j次埃式筛筛掉了\(P_j\)的倍数，他们的最小质因子都是\(P_j\),所以
\[
\begin{aligned}
x&=\sum_{i=2P_j}^nh(i)[M(i)=P_j]
\\&=\sum_{i=2}^{\frac{n}{P_j}}h(iP_j)[M(iP_j)=P_j]
\\&=h(P_j)\sum_{i=2}^{\frac{n}{P_j}}h(i)[M(i)\ge P_j]
\\&=h(P_j)\sum_{i=2}^{\frac{n}{P_j}}h(i)[M(i)\gt P_{j-1}]
\\&=h(P_j)(\sum_{i=2}^{\frac{n}{P_j}}h(i)[M(i)\gt P_{j-1}或i \in primes]-\sum_{i=1}^{j-1}h(P_i))
\\&=h(P_j)(g(\frac{n}{P_j},j-1)-\sum_{i=1}^{j-1}h(P_i))
\end{aligned}
\]
最后就成了这个
\[
\begin{aligned}
g(n,j)=\left\{\begin{matrix}
g(n,j-1)-h(P_j)(g(\frac{n}{P_j},j-1)-\sum_{i=1}^{j-1}h(P_i))&M(n)\le P_j\\
g(n,j-1)& M(n)\gt P_j
\end{matrix}\right.
\end{aligned}
\] 到这里就已经可以记忆化递归解决了,但是递归比较慢,我们考虑把它变成非递归,我们观察这个式子。
我们发现我们可以先枚举j因为\(g(n,j)\)是由\(g(?,j-1)\)推导过来的，然后从大到小枚举n，来更新数组，又因为n的前一项可能与\(\frac{n}{P_j}\)有关，所以我们可以把他们都用map映射一下，再进一步分析，根据整除分块的传递性，\(\frac{\frac{a}{b}}{c}=\frac{a}{bc}\)我们可以得出所有\(g(x,y)\)中x构成的集合，恰好是集合\(\{x|x=\frac{n}{t},t\in [1,n]\}\),最后预处理一下\(\sum^{j-1}_{i=1}h(P_i)\)即可，对于整除分块的映射，我们又可以加速到O(1)此处不做过多分析。
最后我们得到了这个\(O(\frac{n^{\frac{3}{4}}}{lg(n)})\)算法
再看复杂一些的第二类函数
第二类函数是抽象的积性函数\(f\)。
如果我们能够通过一些方法求出\(\sum_{i=1}^{n}f(P_i)\)和\(f(P_i^k)\),那么我们就能够很简单得推出f的前缀和。
对于\(\sum_{i=1}^{n}f(P_i)\), 我们这样来求，比如说f(x)在x是一个质数的时候能表示为某个简单多项式，那么我们就可以通过将多项式函数看做某些幂函数的线形组合，先求出幂函数各自的质数前缀和，然后相加就可以得到f的质数前缀和。
而对于另外一个\(f(P_i^k)\)则需要通过函数的定义来求了。
现在假设我们已经预处理出了\(\sum_{i=1}^xf(P_i)(x \in n的数论分块即x=\frac{n}{?})其实就是g(x,\infty)\)。
我们设\(\begin{aligned}S(n,j)=\sum_{i=2}^nf(i)[M(i)\ge P_j]\end{aligned}\)注意和\(g(n,j)\)对比。
\[
\begin{aligned}
&S(n,j)
\\=&\sum_{i=j}^{P_i\le n}f(P_i)+f(P_i)S(\frac{n}{P_j},j+1)+f(P_i^2)S(\frac{n}{P_i^2},j+1)+f(P_i^3)S(\frac{n}{P_i^3},j+1)+...
\end{aligned}
\] 这里已经可以了，第一项可以通过两个前缀和相减得到，后边的递归。这就是min25筛的灵魂所在。
我们现在好好来分析一下这个递归式子。我们发现第一项是最好求的，就是第一类函数，但是后边的几项必须要求积性函数。这也是min25筛只能对积性函数起作用的地方。
min25筛能处理更多的函数吗？
我们暂定这些函数为f，显然我们必须要能够求出g和s，这就是min25筛,对于g，这里不对此作过多分析，没有这个必要，我们假定都是一类与幂函数线形组合有关的函数，抑或是某几项与幂函数有关，反正只要能够找到完全积性函数h在质数自变量和f函数存在相等关系即可。s的话，第一项简单差分，后边的看似要求f是积性函数，其实不然，我们仔细分析，其实他要求的是这样的要求: 假定y是x的最小质因子，\(z=y^k且z｜x且k最大\)，我们只要能够通过\(f(z)和f(\frac{x}{z})\)这两项能够推出f(x)即可，这里并没有强制要求\(f(x)=f(z)*f(\frac{x}{z})即f(x)=f(M(x))\)。举个例子，若\(f(x)=f(z)=f(y)=y\)，我们也是可以求的。
贴一个求\(f(a^b)=a \bigotimes b\)和\(f(x)=M(x)\)的代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
using namespace std;
typedef long long ll;
const ll sqr=2e5+10;// 2sqrt(n)
ll p[sqr],np[sqr]={1,1};
void prime_ini(){// 素数不可能筛到longlong范围
for(int i=2; i<sqr; i++){
if(!np[i])p[++p[0]]=i;//把质数收录
for(int j=1; 1ll*i*p[j]<sqr; j++){
np[i*p[j]]=1;//对每一个数字枚举他的最小因子
if(i%p[j]==0)break;//在往后的话就不是最小因子了
}
}
}
const ll mod=1e9+7;
ll w[sqr],g[sqr][2],sp[sqr][2],id1[sqr],id2[sqr],mpn;
inline ll& mp(ll x){return x<sqr?id1[x]:id2[mpn/x];}
void min25(ll n){// 计算质数位置之和的时候 只用到了f(x,1) 和 oddsum(x)
mpn=n;
ll m=0;
for(ll l=1,r;l<=n;l=r+1){// i从小到大 n/i从到小
r=n/(n/l);
mp(n/l)=++m;
w[m]=n/l;
g[m][0]=(w[m]-1)%mod;// f(x)=1, s(x)=x
g[m][1]=(__int128(w[m])*(w[m]+1)/2-1)%mod; // f(x)=x, s(x)=x(x+1)/2 这里的int128非常关键，因为n是1e10级别的
}//assert(w[m]==1);
for(ll j=1;p[j]*p[j]<=n;j++){
sp[j][0]=sp[j-1][0]+1;// f(x)=1
sp[j][1]=(sp[j-1][1]+p[j])%mod;// f(x)=x
for(ll i=1;w[i]>=p[j]*p[j];++i){// w[i]从大到小 当i等于m的时候 w[i]>=p[j]*p[j]恒不成立
g[i][0]-=(g[mp(w[i]/p[j])][0]-sp[j-1][0])*1;// f(x)=1
g[i][1]-=(g[mp(w[i]/p[j])][1]-sp[j-1][1])*p[j];// f(x)=x
g[i][0]=(g[i][0]%mod+mod)%mod;
g[i][1]=(g[i][1]%mod+mod)%mod;
}
}
}
// f(pow(a,b))=a^b f为积性函数
inline ll f(ll a,ll b){return a^b;} // 当且仅当a是一个素数
ll s(ll n,ll j){// sum of f(x) x<=n minfac(x)>=p[j]
ll res=(g[mp(n)][1]-g[mp(n)][0])-(sp[j-1][1]-sp[j-1][0])+2*mod;// 减掉p[j]前面的质数 ： [p[j],n]上的质数的函数的和
if(n>=2&&j==1) res+=2;
for(ll k=j;p[k]*p[k]<=n;k++){// 枚举的最小质因子
for(ll x=p[k],e=1;x*p[k]<=n;x*=p[k],e++){//枚举该因子出现次数
res+=s(n/x,k+1)*f(p[k],e)%mod+f(p[k],e+1);// 每次增加2mod res不可能超过 long long
}
}
return res%mod;
}
// f(x)=minfac(x) f不为积性函数 但我们用积性函数来做他
typedef pair<ll,ll> pll;
pll s2(ll n,ll j){//
ll res1=g[mp(n)][0]-sp[j-1][0]+2*mod;
ll res2=g[mp(n)][1]-sp[j-1][1]+2*mod;// 减掉p[j]前面的质数 ： [p[j],n]上的质数的函数的和
for(ll k=j;p[k]*p[k]<=n;k++){// 枚举的最小质因子
for(ll x=p[k],e=1;x*p[k]<=n;x*=p[k],e++){//枚举该因子出现次数
pll tmp=s2(n/x,k+1);
res1+=tmp.first*1%mod+1;
res2+=tmp.first*p[k]%mod+p[k];// 每次增加2mod res不可能超过 long long
}
}
return pll(res1%mod,res2%mod);
}
int main() {
prime_ini();
ll n;
while(cin>>n){
min25(n);
if(n==1) cout<<1<<endl;
else cout<<(s(n,1)+1)%mod<<endl;
}
}