简介
Min_25筛据说可以在处理出含有以下性质的函数f的前缀和:
1.,即f是一个积性函数
2.可以快速计算。
PS:本文没有关于复杂度的证明。。。
预处理
首先要预处理两个东西,一个是(n为询问的值域)内的质数。直接线性筛就好了。用表示第i个质数。设共有个质数
另一个是,表示所有中满足x最小质因子大于或者x是质数的之和。
这样一来,表示的就是中所有质数的f值之和。这个东西后面会用到。
那么来看一下这个值该如何求。
显然,如果那么。因为这时的已经只表示中所有质数的f之和。并不会比多删除掉任何东西。
如果呢?我们可以理解为埃氏筛法的过程,与的差别就是筛掉了的倍数。那么就好像可以转移了。问题就在于如何计算出所有的倍数所产生的贡献。前面说到这是一个积性函数,所以我们将这些要删除的数全都提出来一个,那么剩下的就是了。因为需要是这些数字的最小质因子,所以实际上区间内的数字是不可以的,所以要删除的区间实际上是所以要删除的数字就是。也就是说
因为最终我们需要的只有。所以空间只需要开一维,每次处理复杂度是的(实际上并不到),类似于整除分块,我们知道只有级别种取值。复杂度据说是。
计算答案
上面的东西预处理完了,那么有什么用呢??
我们再定义一个函数表示中满足的最小质因子大于等于的之和。
最终我们要求的答案就是
上面说到,可以表示中所有质数的值之和。
所以我们将分为质数和合数两块来处理。
质数的一块显然就是。为什么要减掉后面这一块??因为小于的质数不包含在里面呀~
然后考虑合数的一块该如何求,我们枚举一下这些合数的最小质因子和的指数。于上方求g的方法类似的,我们可以提出来一个,那么剩下的就是,他们的f之和就是。发现这样无法转移,那么我们只好从转移过来,但是这样就没被计算,单独加上就好了。
综上所述,
然后递归计算即可。这里的复杂度据说也是。
经典例题
定义函数满足以下性质,
1.
2.(p为质数)
3.
求。
思路
发现这些性质恰好吻合了我们一开始要求的性质。
发现除2外所有的质数均为奇数,所以就有(p为奇质数)。然后发现这个东西并不是积性函数,没法预处理g了。怎么办?
那就把它拆开,拆成,那么就有。然后按照上述方法分别预处理除关于的。关于的。
要说明的是,我们一开始将所有的合数全都当成奇质数来处理,因为最后都要“筛”掉的,所以没有影响。
具体细节:
预处理g时,有个式子是,也就是前个质数的前缀和。所以预处理质数时同时预处理一下前缀和。
code
/* * @Author: wxyww * @Date: 2019-12-22 17:42:00 * @Last Modified time: 2019-12-24 21:58:42 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 2000010,mod = 1e9 + 7; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int tot; ll n,m,w[N],pri[N],sum[N],js,vis[N],g[N],h[N]; void pre() {//筛出质数 for(int i = 2;i <= m;++i) { if(!vis[i]) { pri[++js] = i; sum[js] = sum[js - 1] + i; sum[js] %= mod; } for(int j = 1;j <= js && i * pri[j] <= m;++j) { vis[pri[j] * i] = 1; if(i % pri[j] == 0) break; } } } int id1[N],id2[N]; ll S(ll now,int x) { if(now <= 1 || pri[x] > now) return 0; // printf("%lld %d\n",now,x); int k; if(now <= m) k = id1[now]; else k = id2[n / now]; ll ret = (g[k] - h[k] - sum[x - 1] + x - 1) % mod; if(x == 1) ret += 2;//f(2)当作1计算,实际上f(2)=3 for(int k = x;k <= js && pri[k] * pri[k] <= now;++k) { ll p = pri[k]; for(int e = 1;p * pri[k] <= now;p = p * pri[k],++e) { ret += (pri[k] ^ e) * S(now / p,k + 1) % mod + (pri[k] ^ (e + 1)); ret %= mod; } } return ret; } int main() { // freopen("1.in","w",stdout); n = read(); m = sqrt(n); pre(); // puts("!!!"); for(ll l = 1,r;l <= n;l = r + 1) { r = n / (n / l); ll tmp = n / l; w[++tot] = tmp; if(tmp <= m) id1[tmp] = tot;//数组不够大,通过id1和id2来映射到sqrt(n)以内 else id2[n / tmp] = tot; g[tot] = (tmp + 2) % mod * ((tmp - 1) % mod) % mod; if(g[tot] & 1) g[tot] += mod; g[tot] /= 2; // g[tot] %= mod; h[tot] = tmp - 1; } // for(int i = 1;i <= tot;++i) printf("%lld ",g[i]); for(int j = 1;j <= js;++j) { for(int i = 1;i <= tot && pri[j] * pri[j] <= w[i];++i) {//枚举顺序不能颠倒 ll tmp = w[i] / pri[j]; int k; if(tmp <= m) k = id1[tmp]; else k = id2[n / tmp]; g[i] -= pri[j] * (g[k] - sum[j - 1]) % mod;//枚举顺序不能颠倒的原因 g[i] %= mod; h[i] -= (h[k] - (j - 1)); h[i] %= mod; } } // cout<<g[tot - 2]<<endl; cout<<(S(n,1) + 1 + mod) % mod;//单独把1算上 return 0; }