UOJ

分析

题目要求的就是 $[l,r]$ 中的数的次大质因子的和，这里的次大是可重集的次大。

首先对其差分，变为求 $[1, n]$ 中的数的次大质因子之和。

这个数据范围启发我们考虑一些筛法，仔细思考之后发现只能考虑 Min_25 筛。

然而直接做显然是不行的。我们需要对其第二部分即求答案的部分进行一些改造，使得它能求出我们想求的东西。

对于一个合数，我们在其剩余的质因子个数 $\leq 1$ 时计算其贡献。

在计算 $S(n, j)$ 时，剩余的质因子个数 $\leq 1$ 的合数的个数很好求出，而其次大质因子为 $p_{j - 1}$（因为 $S(n, j)$ 一定是从 $S(?, j - 1)$ 走过来的）；而对于剩下的合数，我们仍然枚举最小质因子和次数递归计算即可。

为了求出剩余的质因子个数 $\leq 1$ 的合数的个数，我们需要在第一部分对每个 $\left\lfloor\frac{n}{i}\right\rfloor$ 求出小于等于其的质数个数。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

ll read() {
    ll X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 640000;

ll n, w[N], g[N];
int S, id1[N], id2[N], top;

int p[N], v[N], pcnt = 0;
void sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) p[++pcnt] = i;
        for (int j = 1; j <= pcnt && i * p[j] <= n; ++j) {
            v[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}

ll S_(ll x, int j) {
    if (x <= 1 || p[j] > x) return 0;
    int k = x <= S ? id1[x] : id2[n / x];
    ll res = p[j - 1] * (g[k] - (j - 1));
    for (int i = j; i <= pcnt && 1ll * p[i] * p[i] <= x; ++i) {
        ll p1 = p[i], p2 = 1ll * p[i] * p[i];
        for (int e = 1; p2 <= x; ++e, p1 = p2, p2 *= p[i])
            res += S_(x / p1, i + 1) + p[i];
    }
    return res;
}

ll solve(ll n_) {
    pcnt = top = 0;
    n = n_; sieve(S = sqrt(n));
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        w[++top] = n / l, g[top] = n / l - 1;
        if (n / l <= S) id1[n / l] = top;
        else id2[n / (n / l)] = top;
    }
    for (int i = 1; i <= pcnt; ++i)
        for (int j = 1; j <= top && 1ll * p[i] * p[i] <= w[j]; ++j) {
            ll x = w[j] / p[i]; int k = x <= S ? id1[x] : id2[n / x];
            g[j] -= g[k] - (i - 1);
        }
    return S_(n, 1);
}

int main() {
    ll l = read(), r = read();
    printf("%lld\n", solve(r) - solve(l - 1));
    return 0;
}