题意：次小素因子前缀和。

类似 PE 521 求最小素因子前缀和，虽然不是积性函数，但不妨碍我们筛。

令 S(n, k) 表示次小质因子 >= P[k] 时的前缀和（P[0] = 0)。
转移，分两种情况：
1. 剩余部分是一个更大的素数，贡献是，p * (g[id(n)] – g[p])。
2. 枚举最小因子分解，递归。

#include <lastweapon/io>
using namespace std;

const int N = int(1e6) + 9;
LL n; int nn; int P[N], Pn;
LL di[N], g[N]; int dn;
inline int id(LL x) {return x <= nn ? x : dn-n/x+1;}

LL S(LL n, int k) {
    int p = P[k]; if (n <= p) return 0;
    LL z = p * (g[id(n)] - g[p]);
    FOR_1(i, k+1, Pn) {
        LL p = P[i]; if (p*p > n) break;
        for (LL j=n/p;j>=p;j/=p) {
            z += S(j, i) + p;
        }
    }
    return z;
}

LL S(LL n) {
    ::n = n; nn = sqrt(n); Pn = dn = 0;
    for (LL i=1,j;i<=n;i=j+1) {
        di[++dn] = j = n/(n/i);
        g[dn] = j-1;
    }
    FOR_1(p, 2, nn) if (g[p] != g[p-1]) {
        P[++Pn] = p; for (LL i=dn,ii=di[i];(LL)p*p<=ii;ii=di[--i]) {
            g[i] -= g[id(ii/p)] - g[p-1];
        }
    }
    if (!Pn) return 0;
    return S(n, 0);
}

int main(){
    LL l, r; RD(l, r);
    cout << S(r) - S(l-1) << endl;
}

Posted by xiaodao
Category: 日常