min_25筛

(Updated: )
(5 mins to read)

当f$f(i)$是一个积性函数，且$f(p)$是一个关于p的低阶多项式，$f(p^k)$是一个容易计算的式子，那么就可以利用该亚线性筛，快速算出$\sum_{i=1}^nf(i)$，$n \leq 10^{11}$

第一步

利用另一个函数$g(n,j)$，快速计算出f在质数处的前缀和

$g(n, j) = \sum \limits_{i=1}^n [i \ is \ prime || minp > p_j] i^k$

表示$\leq n$中的所有质数以及最小质因子大于第j小质数$p_j$​的所有数的k次方和，因为f(p)是一个关于p的多项式，这样我们把这个多项式拆成单项式，再取不同的k，而当$p_j$​等于最后一个小于等于$\sqrt n​$的质因子时，$g(n, j)$就表示小于等于n的所有质数的k次方和了。一个数的最小质因子一定是$\leq \sqrt n$​的考虑从$g(n, j-1)$转移到$g(n, j)$时，只需要去掉最小质因子$=p_j$​的所有合数即可

$g(n, j) = g(n, j-1) -p_j^k(g(\frac{n}{p_j}, j-1) - g(p_{j-1}, j-1))$

其中$g(p_{j-1}, j-1)$表示前$j-1$个质数的k次方和，可以在线性筛的时候预处理出来在转移的时候我们只需要用到$\lfloor \dfrac{n}{x} \rfloor$处的取值，而这种值的个数是$O(\sqrt n)$级别的，可以利用一个id1数组和一个id2数组映射一下，对于$\leq \sqrt n$​的数，存在id1里，对于其他数存在id2中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ll w[M], g1[M], g2[M];
int id1[M], id2[M];
auto id = [&](ll x) { return x<=B ? id1[x] : id2[n/x]; };
void solve(ll _n)
{
  int sz = 0;
  n = _n, B = sqrt(n) + 1;
  getprime(B);
  for(ll l=1, r, v; l<=n; l=r+1)
  {
    v = n/l, r = n/v;
    w[++sz] = v; g1[sz] = prex1(v); g2[sz] = prex2(v);
    if(v<=B) id1[v] = sz; else id2[r] = sz;
  }
  for(int i=1; i<=pc; i++)
  {
    for(int j=1; j<=sz&&1ll*pr[i]*pr[i]<=w[j]; j++)
    {
      int t = id(w[j]/pr[i]);
      g1[j] = ((g1[j] - (g1[t] - sp1[i-1])*x1(pr[i]))%mod + mod)%mod;
      g2[j] = ((g2[j] - (g2[t] - sp2[i-1])*x2(pr[i]))%mod + mod)%mod;
    }
  }
}

通过这一步我们就可以求f在质数处的前缀和了，如果要快速统计质数个数，答案就是$g_{id(n)}$​

第二步

同样的，设$S(n,k)$表示求所有质因子大于$p_k$​的数(大于$p_k$​的质数也算)的函数f之和，答案就是$S(n,0)$

$S(n,x) = g(n) - sp_x + \sum\limits_{p_k^e \leq n \land k>x} f(p_k^e)S(\frac{n}{p_k^e} + [e \neq 1])$

其中$g(n)-sp_x$​表示大于$p_k$​的质数的函数f之和，这在第一步中已经预处理出来，再枚举合数中最小质因子的大小以及幂次，递归处理即可，注意我们在所有计算中都是不统计1处的答案的，所以当$e\gt 1$时，要额外算上$f(p_k^e)$)处的值

1
2
3
4
5
6
7
8
9
ll go(ll x, int k)
{
  if(pr[k]>=x) return 0;
  int t = id(x); ll ans = (f(g1[t]-sp1[k], g2[t]-sp2[k])%mod + mod)%mod;
  for(int i=k+1; i<=pc&&1ll*pr[i]*pr[i]<=x; i++)
    for(ll pp=pr[i], e=1; pp<=x; e++, pp=pp*pr[i])
      ans = (ans + fp(pp%mod)*(go(x/pp, i)+(e!=1)))%mod;
  return (ans+mod)%mod;
}

最后的答案就是go(n, 0)+f(1)了