UR#13 SRAND

总感觉这位大仙讲的很清楚：bztminamoto

题意

题目讲的是求 l~r 内所有数的次大质因子，这里设 f(x) 为 x 的次大质因子

我们差分一下就变成求两个前缀和信息了

按照套路，我们考虑 S(i,j) 表示小于等于 i 的数内，所有最小质因子小于等于 p[j] 的次大质因子的前缀和

然后我们考虑将所有数分为合数与质数，那么质数的次大质因子为 0 ，无贡献

至于合数就是枚举它的最小质因子，那么枚举到 pk （k>=j）时，我们有两种情况：

1. 当前的 pk 是次大质因子，那么最大质因子可能为 pk~ \(\lfloor {i\over p_k^{~e}} \rfloor\) 内任意的质数（e 满足： \(p_k^{e+1}<=i\)）的可能 ，所以加上贡献这个范围内质数个数的贡献
2. 当前 pk 不是次大质因子，那么我们加上 \(S({i\over p_k^{~e}},k+1)\) 即可

//by Judge
#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=(a),I=(b)+1;i<I;++i)
#define ll long long
using namespace std;
const int M=8e5+3;
typedef ll arr[M];
ll L,R,m,tot,blo; arr v,p,w,g,id1,id2;
inline void prep(int n){
for(int i=2;i<=n;++i){ if(!v[i]) p[++tot]=i;
for(int j=1;j<=tot&&p[j]*i<=n;++j)
{v[i*p[j]]=1; if(!(i%p[j])) break;}
}
}
inline ll S(ll n,ll x,int y){
if(x<=1||p[y]>x) return 0;
int k=x<=blo?id1[x]:id2[n/x]; ll res=0;
for(int i=y;i<=tot&&1ll*p[i]*p[i]<=x;++i){
ll t1=p[i],t2=t1*t1;
for(int e=1;t2<=x;++e,t1=t2,t2*=p[i]){
int k=x/t1<=blo?id1[x/t1]:id2[n/(x/t1)];
res+=S(n,x/t1,i+1)+p[i]*(g[k]-i+1);
}
} return res;
}
inline ll solv(ll n){ tot=m=0,prep(blo=sqrt(n)); // g 里存质因子个数的前缀和
for(ll l=1,r;l<=n;l=r+1) r=n/(n/l),w[++m]=n/l,g[m]=w[m]-1,
(w[m]<=blo)? id1[w[m]]=m:id2[n/w[m]]=m;
fp(j,1,tot) for(int i=1,k;1ll*p[j]*p[j]<=w[i]&&i<=m;++i)
k=w[i]/p[j]<=blo?id1[w[i]/p[j]]:id2[n/(w[i]/p[j])],g[i]-=g[k]-j+1;
return S(n,n,1);
}
int main(){ cin>>L>>R,cout<<solv(R)-solv(L-1); return 0; }