BZOJ 5244.「FJWC2018」最大真因数

显然一个合数的最大真因子等于它自身除以它的最小质因子。
这个很容易用欧拉筛来求,然鹅 lr5109l \le r \le 5 \cdot 10^9……

首先转化为前缀和相减,问题变成求所有不大于 nn 的正整数的最大真因子。

欧拉筛不是很好优化,但是如果是埃筛,可以扩展到亚线性复杂度(即阉割的 Min25 筛)。
我们考虑用 Min25 筛的做法来求不大于 nn 的质数之和
为什么不直接求呢?因为这个算法本来是用来筛积性函数在质数处的点值的。

观察这个算法递推式的推导过程,其实第 kk 轮转移减去的数就是埃筛第 kk 轮筛去的数之和。
然鹅我们发现,这些数刚好就是所有最小质因子为 pkp_k 的数(其中 pkp_k 表示第 kk 个质数)。
于是在转移的时候另外统计一下答案,即直接把减去的数除以 pkp_k 后加入答案。

(我觉得这道题是熟悉 Min25 筛思想的好题)

代码:

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
#include <cstdio>
#include <cmath>
using namespace std;
const long long N = 5e9;
const int MX = 71e3;
long long l,r;
int vis[MX + 5],cnt,prime[MX + 5];
long long Gprime[MX + 5];
namespace solver
{
long long n;
int lim;
int tot,le[MX + 5],ge[MX + 5];
long long lis[2 * MX + 5];
inline int &id(long long x)
{
return x <= lim ? le[x] : ge[n / x];
}
long long G[2 * MX + 5],F[2 * MX + 5];
long long calc(long long m)
{
if(!m)
return 0;
tot = 0,n = m,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] = (n / l + 2) * (n / l - 1) / 2,F[tot] = 0;
}
for(register int k = 1;k <= cnt;++k)
{
int p = prime[k];
long long s = (long long)prime[k] * prime[k];
for(register int i = 1;lis[i] >= s && i <= tot;++i)
F[i] += G[id(lis[i] / p)] - Gprime[k - 1],G[i] -= p * (G[id(lis[i] / p)] - Gprime[k - 1]);
}
return F[1];
}
}
int main()
{
for(register int i = 2;i <= MX;++i)
{
if(!vis[i])
prime[++cnt] = i,Gprime[cnt] = Gprime[cnt - 1] + i;
for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
}
}
scanf("%lld%lld",&l,&r);
printf("%lld\n",solver::calc(r) - solver::calc(l - 1));
}