题目概述

求 $\sum_{i=L}^{R}f(i)$ ，$f(n)$ 表示 $n$ 的次大质因子（相同质因子算多次），若次大质因子不存在则 $f(n)=0$ 。

解题报告

Min_25筛的膜法…… $f(n)$ 并不是个积性函数，但是我们发现可以通过枚举一个素数，然后分别计算这个素数乘上另一个素数或者一个合数的贡献，这可以对应到Min_25筛 $S(n,j)$ 的计算方法。

由于 $S(n,j)$ 上一个素数是 $p_{j-1}$ ，因此乘上素数的贡献是 $p_{j-1}[g_n-(j-1)]$ ，$g_n$ 是预处理出的素数个数。

如果乘上一个合数，那么显然 $p_{j-1}$ 将不会成为次大质因数，所以直接统计 $S(\lfloor{n\over p_i^k}\rfloor,i+1)+f(p_i^{k+1})$ 即可。

示例程序

#include<cmath>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxs=632456;

int S;int p[maxs+5];bool pri[maxs+5];
int m,ID[2][maxs+5];LL L,R,n,a[maxs+5],g[maxs+5];

inline void Make(int n){
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=n;j++)
            {pri[t]=true;if (!(i%p[j])) break;}
    }
}
#define ID(x) ((x)<=S?ID[0][x]:ID[1][n/(x)])
LL Sum(LL a,int b){
    if (a<=1||p[b]>a) return 0;int k=ID(a);LL ans=(b>1?(LL)p[b-1]*(g[k]-(b-1)):0);
    for (int i=b;i<=p[0]&&(LL)p[i]*p[i]<=a;i++){
        LL A=p[i],B=A*A;
        for (int j=1;B<=a;j++,A=B,B*=p[i])
            ans+=Sum(a/A,i+1)+p[i];
    }return ans;
}
inline LL Min25(LL x){
    n=x;S=sqrt(n);m=0;
    for (LL l=1,r;l<=n;l=r+1){
        r=n/(n/l);a[++m]=n/l;g[m]=a[m]-1;
        a[m]<=S?ID[0][a[m]]=m:ID[1][n/a[m]]=m;
    }
    for (int j=1;j<=p[0]&&p[j]<=S;j++)
        for (int i=1;i<=m&&(LL)p[j]*p[j]<=a[i];i++)
            g[i]+=j-1-g[ID(a[i]/p[j])];
    return Sum(n,1);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%lld%lld",&L,&R);Make(maxs);printf("%lld\n",Min25(R)-Min25(L-1));return 0;
}