简介#
Min_25筛据说可以在O(
n
3
4
logn
)处理出含有以下性质的函数f的前缀和:
1.f(ab)=f(a)f(b)，即f是一个积性函数
2.f(pk)可以快速计算。
PS:本文没有关于复杂度的证明。。。
预处理#
首先要预处理两个东西，一个是
√
n
(n为询问的值域)内的质数。直接线性筛就好了。用pri[i]表示第i个质数。设共有m个质数
另一个是g(n,j)，表示所有x∈[1,n]中满足x最小质因子大于pri[j]或者x是质数的f(x)之和。
这样一来，g(n,m)表示的就是[1,n]中所有质数的f值之和。这个东西后面会用到。
那么来看一下这个g值该如何求。
显然，如果pri
2
j
>n那么g(n,j)=g(n,j−1)。因为这时的g(n,j−1)已经只表示[1,n]中所有质数的f之和。g(n,j)并不会比g(n,j−1)多删除掉任何东西。
如果pri
2
j
≤n呢？我们可以理解为埃氏筛法的过程，g(n,j)与g(n,j−1)的差别就是筛掉了prij的倍数。那么就好像可以转移了。问题就在于如何计算出所有prij的倍数所产生的贡献。前面说到这是一个积性函数，所以我们将这些要删除的数全都提出来一个prij，那么剩下的就是[1,
n
prij
]了。因为需要prij是这些数字的最小质因子，所以实际上区间[1,prij−1]内的数字是不可以的，所以要删除的区间实际上是[prij,
n
prij
]所以要删除的数字就是f(prij)[g(
n
prij
,j−1)−g(prij−1,j−1)]。也就是说g(n,j)=g(n,j−1)−f(prij)[g(
n
prij
,j−1)−g(prij−1,j−1)]
因为最终我们需要的只有g(⌊
n
i
⌋,m),1∈[1,n]。所以空间只需要开一维，每次处理复杂度是O(m)的（实际上并不到），类似于整除分块，我们知道
n
i
只有
√
n
级别种取值。复杂度据说是O(
n
3
4
logn
)。
计算答案#
上面的东西预处理完了，那么有什么用呢？？
我们再定义一个函数S(n,j)表示x∈[1,n]中满足x的最小质因子大于等于prij的f(x)之和。
最终我们要求的答案就是S(n,1)+f(1)
上面说到，g(n,m)(pri
2
m
>n)可以表示[1,n]中所有质数的f值之和。
所以我们将S(n,j)分为质数和合数两块来处理。
质数的一块显然就是g(n,m)−
j−1
∑
k=1 f(prik)。为什么要减掉后面这一块？？因为小于prij的质数不包含在S(n,j)里面呀~
然后考虑合数的一块该如何求，我们枚举一下这些合数的最小质因子k∈[prij,prim]和k的指数e。于上方求g的方法类似的，我们可以提出来一个pri
e
k
，那么剩下的就是[1,
n
pri
e
k
]，他们的f之和就是S(
n
pri
e
k
,k)。发现这样无法转移，那么我们只好从S(
n
pri
e
k
,k+1)转移过来，但是这样f(pri
e+1
k
)就没被计算，单独加上就好了。
综上所述，
S(n,j)=g(n,m)−
j−1
∑
k=1 f(prik)+
m
∑
k=j
pri
e+1
k
≤n
∑
e=1 (f(pri
e+1
k
)+f(pri
e
k
)S(
n
pri
e
k
,k+1)
然后递归计算即可。这里的复杂度据说也是O(
n
3
4
logn
)。
经典例题#
loj6053简单的函数
定义函数f(x)满足以下性质，
1.f(1)=1
2.f(pc)=p⊗c(p为质数)
3.f(ab)=f(a)f(b)（a,b互质）
求
n
∑
i=1 f(i)。n≤1010
思路#
发现这些性质恰好吻合了我们一开始要求的性质。
发现除2外所有的质数均为奇数，所以就有f(p)=p−1（p为奇质数）。然后发现这个东西并不是积性函数，没法预处理g了。怎么办？
那就把它拆开，拆成f1(p)=p,f2(p)=1,那么就有f(p)=f1(p)−f2(p)。然后按照上述方法分别预处理除关于f1的g(n,m)。关于f2的h(n,m)。
要说明的是，我们一开始将所有的合数全都当成奇质数来处理，因为最后都要“筛”掉的，所以没有影响。
具体细节：
预处理g时，有个式子是g(prij−1,j−1)，也就是前j−1个质数的前缀和。所以预处理质数时同时预处理一下前缀和。
code#
Copy
/*
* @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;
}
本文转自于网络
|
|
收藏
淘帖
踩
