Min_25 太神仙了!
据说这个筛法的复杂度是 或 的。(别问我 是啥,问就不知道
本质上其实是扩展埃筛。
感谢 chd 哥哥让我学会 Min_25 筛!(@Trisolaris
筛啥用的?
积性函数前缀和,不然用着干啥(
要求被筛的函数 在质数 处的值 的值为一个关于 的低次多项式,在 处的值 可以快速计算。
记号
- 表示全体质数的集合。
- 本文一般默认 。
- 为第 小的质数。特别地,。
- 表示 的最小质因子(即 Least Prime Factor
怎么筛?
假设我们已经算出了所有 ,可以发现答案就是 。
求 F
枚举最小质因子及其指数可得
看起来非常的迷,接受不了。
第一个等号后,第一个和式的意思就是枚举最小质因子,并且显然每个合数的最小质因子一定在 内。
第二项是补回质数的贡献,因为 时没有计 的贡献。
第二个等号后只是把第二项根据定义拆成前缀和的形式。
最后一个等号比较奇怪。
注意到若 ,显然有 ,故 。
假设已经求得了所有 ,现在理论上有两种方法计算 ,根据上式直接递归就是其中一种。
Yet Another F
话说其实 Min_25 筛有无数种实现方式……重要的是埃氏筛的思想。
所以我也不知道从哪里看来的改成递推形式要换 的定义(逃
(如果不换的话也从上式能导出比较显然的递推式,不过也许这种更好写?
令
易知答案同样为 。
考虑一个递推式
于是同样地枚举最小质因子即可。
边界条件为 。
似乎因为指数不会很大所以复杂度仍然是 。
求 f 在质数处的值
根据递推式可以发现实际上需要用到的 只有形如 的 处。
根据条件, 可以写作 。
故我们可以分别讨论每一项的贡献。
设 。
熟悉埃筛的话,你会发现这相当于是埃筛筛了 轮后剩下的数的 次方之和。
最后我们想要的实际上就是 ,其中 表示 。
因为一个合数的最小质因子肯定不会超过 。
考虑转移。
对于 ,并没有筛掉新的数,故直接转移即可。
对于 ,筛掉的数显然有质因子 ,故减去 。
然鹅我们筛掉的应该是 的 ,故要考虑 的 的贡献。
实际上就是加回 。
综上所述,有
复杂度?
并不会证明,由论文可得求 的复杂度为 (第一种方法)。
求 的复杂度为 (第二种方法的复杂度也长这样)。
一些提示
很多东西可以直接欧拉筛预处理,至于是啥,自己想想。
例题 - LibreOJ 6053.简单的函数
注意到质数除了 都是奇数,故 。
于是有 。
然后对 讨论一下即可。
递归写法的代码见 https://www.alpha1022.me/articles/loj-6053.htm
Yet Another F 中的写法代码:
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
using namespace std;
const long long N = 1e10;
const int MX = 1e5;
const int mod = 1e9 + 7;
const int inv = 5e8 + 4;
long long n;
int lim;
int vis[MX + 5],prime[MX + 5],cnt,Gprime[MX + 5];
int tot,le[MX + 5],ge[MX + 5];
long long lis[2 * MX + 5];
int G[2 * MX + 5][2],F[2 * MX + 5];
inline int &id(long long x)
{
return x <= lim ? le[x] : ge[n / x];
}
int main()
{
for(register int i = 2;i <= MX;++i)
{
if(!vis[i])
prime[++cnt] = i,Gprime[cnt] = (Gprime[cnt - 1] + i) % mod;
for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
}
}
scanf("%lld",&n),lim = sqrt(n);
for(register long long l = 1,r;l <= n;l = r + 1)
{
r = n / (n / l);
lis[id(n / l) = ++tot] = n / l;
G[tot][0] = (n / l % mod - 1 + mod) % mod,G[tot][1] = (n / l % mod + 2) * (n / l % mod - 1 + mod) % mod * inv % mod;
}
for(register int k = 1;k <= cnt;++k)
{
int p = prime[k];
long long s = (long long)p * p;
for(register int i = 1;lis[i] >= s;++i)
G[i][0] = (G[i][0] - (G[id(lis[i] / p)][0] - (k - 1) + mod) % mod + mod) % mod,
G[i][1] = (G[i][1] - (long long)p * ((G[id(lis[i] / p)][1] - Gprime[k - 1] + mod) % mod) % mod + mod) % mod;
}
for(register int i = 1;i <= tot;++i)
F[i] = (G[i][1] - G[i][0] + mod) % mod;
for(register int k = cnt;k;--k)
{
int p = prime[k];
long long s = (long long)p * p;
for(register int i = 1;lis[i] >= s;++i)
{
long long pw = p,pw2 = s;
for(register int c = 1;pw2 <= lis[i];++c,pw = pw2,pw2 *= p)
F[i] = (F[i] + (long long)(prime[k] ^ c) * (F[id(lis[i] / pw)] - (Gprime[k] - k + mod) + mod) % mod + (prime[k] ^ c + 1)) % mod;
}
}
printf("%d\n",(F[1] + 1 + (n >= 2) * 2) % mod);
}