Sol
设 \(f_i\) 表示 \(i\) 的次大质因子
题目就是要求
\[\sum_{i=l}^{r}f_i
\]
考虑求 \(\sum_{i=1}^{n}f_i\)
所求的东西和质因子有关，考虑 \(min25\) 筛的那一套理论
设 \(s(n,j)=\sum_{i=1}^{n}[low_i\ge p_j]f_i\)，其中 \(low_i\) 表示 \(i\) 的最小质因子，\(p_j\) 为第 \(j\) 个质数
那么考虑枚举最小质因子转移
首先如果 \(p_k\) 不是次大质因子，那么
\[S(n,j)=\sum_{k\ge j}\sum_{e=1}^{p_k^{e+1}\le n}S(\lfloor\frac{n}{p^{e}_k}\rfloor,k+1)
\]
如果 \(p_k\) 是次大质因子，那么还要加上
\[p_k\sum_{i=p_k}^{\lfloor\frac{n}{p^{e}_k}\rfloor}[i\in P]
\]
其中 \(P\) 表示质数集合
用 \(min25\) 筛筛出质数个数然后套用上面的方法就好了
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(1e6 + 5);
int pr[maxn], tot, id1[maxn], id2[maxn], d, cnt;
bitset <maxn> ispr;
ll n, f[maxn], val[maxn];
inline void Sieve(int mx) {
register int i, j;
for (i = 2, ispr[1] = 1; i <= mx; ++i) {
if (!ispr[i]) pr[++tot] = i;
for (j = 1; j <= tot && pr[j] * i <= mx; ++j) {
ispr[pr[j] * i] = 1;
if (!(i % pr[j])) break;
}
}
}
# define ID(x) (x) <= d ? id1[x] : id2[n / (x)]
ll Calc(ll x, int m) {
if (x <= 2 || pr[m] > x) return 0;
register ll i, ret = 0, t;
for (i = m; i <= tot && (ll)pr[i] * pr[i] <= x; ++i)
for (t = pr[i]; (ll)pr[i] * t <= x; t *= pr[i])
ret += Calc(x / t, i + 1) + (f[ID(x / t)] - i + 1) * pr[i];
return ret;
}
inline ll Solve(ll _n) {
register ll i, j;
for (cnt = 0, d = sqrt(n = _n), i = 1; i <= n; i = j + 1) {
j = n / (n / i), val[++cnt] = n / i;
val[cnt] <= d ? id1[val[cnt]] = cnt : id2[n / val[cnt]] = cnt;
f[cnt] = val[cnt] - 1;
}
for (i = 1; i <= tot && (ll)pr[i] * pr[i] <= n; ++i)
for (j = 1; j <= cnt && (ll)pr[i] * pr[i] <= val[j]; ++j)
f[j] -= f[ID(val[j] / pr[i])] - i + 1;
return Calc(n, 1);
}
ll l, r;
int main() {
scanf("%lld%lld", &l, &r), Sieve(sqrt(r));
printf("%lld\n", Solve(r) - Solve(l - 1));
return 0;
}