题目描述
https://uoj.ac/problem/188
简要题意：给定 $l,r$，求 $\sum_{i=l}^rf(i)$，其中 $f(i)$ 表示 $i$ 的非严格次大质因数，例如 $f(1)=1,f(3^2)=3$
$l,r\le 10^{11}$
Solution
我们考察 $min\underline{}{25}$ 的过程，发现在求 $S(n,m)$ 的时候，我们枚举最小质因子 $p_k^e,k>m$ 时，如果这个 $p$ 有贡献，那么说明剩下数字是质数，那么我们需要 $g(\frac{n}{p_k^e},k)$，这些都可以在 $min\underline{}{25}$ 的时候求出
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
62
|
#include <iostream>
#include <cmath>
#define maxn 1000010
#define ll long long
using namespace std;
int pri[maxn], cnt, sp[maxn]; bool isp[maxn];
void init_isp(int n) {
for (int i = 2; i <= n; ++i) {
if (!isp[i]) pri[++cnt] = i, sp[cnt] = cnt;
for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
isp[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}
ll id1[maxn], id2[maxn]; int Sn; ll n;
int get_id(ll x) { return x <= Sn ? id1[x] : id2[n / x]; }
ll g[maxn], w[maxn]; int num;
void init_min25(ll n) {
num = 0;
for (ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / l); w[++num] = n / l;
g[num] = n / l - 1;
if (w[num] <= Sn) id1[w[num]] = num;
else id2[n / w[num]] = num;
}
for (int i = 1; i <= cnt; ++i)
for (int j = 1; j <= num && 1ll * pri[i] * pri[i] <= w[j]; ++j)
g[j] -= g[get_id(w[j] / pri[i])] - sp[i - 1];
}
ll S(ll n, int m) {
if (pri[m] >= n) return 0;
ll ans = 0;
for (int i = m + 1; i <= cnt && 1ll * pri[i] * pri[i] <= n; ++i)
for (ll x = 1, mul = pri[i]; mul <= n; mul *= pri[i], ++x)
ans += S(n / mul, i) + (x > 1 ? pri[i] : 0) + pri[i] * (pri[i] < n / mul ? g[get_id(n / mul)] - sp[i] : 0);
return ans;
}
ll solve(ll _n) {
n = _n, Sn = sqrt(n), init_min25(n);
return S(n, 0);
}
ll l, r;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> l >> r; init_isp(sqrt(r));
cout << solve(r) - solve(l - 1) << "\n";
return 0;
}
|