不是很能看懂题意，其实就是求\([l,r]\)区间内所有数的次大质因子的和
这可真是看起来有点鬼畜啊
这显然不是一个积性函数啊，不要考虑什么特殊的函数了
我们考虑Min_25筛的过程
设\(S(x,y)\)表示\([1,x]\)内的数满足\(minp(i)>=y\)的数的次大质因子的和
还是分成质数合数以及\(1\)来考虑\(S(x,y)\)
质数和\(1\)都没什么贡献，直接考虑合数
还是枚举最小质因子\(P_k\)以及其出现次数\(e\)
考虑从\(S(\frac{x}{P_k^e},k+1)\)到\(S(x,y)\)如何转移
我们在这里需要计算次大质因子为\(P_k\)的数的贡献
首先这些数得有一个比\(P_k\)大的质因子，同时还得满足比\(P_k\)大的质因子只出现了一次
这样的数除以\(P_k\)的突出特点就是变成了一个质数，而且这个质数大于\(P_k\)
所以我们只需要知道\(\frac{x}{P_k^e}\)内的质数个数就好了
设\(f(i)=\sum_{j=1}^i[j\in P]\)
转移就是
\[S(x,y)=\sum_{k=y}^{P_k^2<=x}\sum_{e=1}^{P_k^e<=x}S(\frac{x}{P_k^e},k+1)+max(0,f(\frac{x}{P_k^e})-k+1)\times P_k
\]
\]
减\(k-1\)是排除掉小于\(P_k\)的质数
最后的答案就是\(S(r,1)-S(l-1,1)\)
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define maxn 1000005
#define re register
#define LL long long
inline LL M(LL x) {return x>0?x:0;}
inline int read()
{
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
LL L,R,Sqr;
LL n,m,w[maxn],tot;
LL p[maxn],g[maxn],id1[maxn],id2[maxn];
int f[maxn];
inline LL S(LL x,int y) {
if(x<=1&&p[y]>x) return 0;
int t=(x<=Sqr)?id1[x]:id2[n/x];
LL ans=0;
for(re int k=y;k<=tot&&p[k]*p[k]<=x;k++) {
LL p1=p[k];
for(re int e=1;p1<=x;e++,p1*=p[k])
ans+=S(x/p1,k+1)+M(g[(x/p1<=Sqr)?id1[x/p1]:id2[n/(x/p1)]]-k+1)*p[k];
}
return ans;
}
inline LL calc(LL T) {
if(T<=1) return 0;n=T;
Sqr=std::sqrt(n)+1;m=0;memset(g,0,sizeof(g));
for(re LL l=1,r;l<=n;l=r+1) {
r=n/(n/l);w[++m]=n/l;
if(w[m]<=Sqr) id1[w[m]]=m;else id2[n/w[m]]=m;
g[m]=w[m]-1;
}
for(re int j=1;j<=tot&&p[j]*p[j]<=n;j++)
for(re int i=1;i<=m&&p[j]*p[j]<=w[i];i++) {
int k=(w[i]/p[j]<=Sqr)?id1[w[i]/p[j]]:id2[n/(w[i]/p[j])];
g[i]=g[i]-g[k]+j-1;
}
return S(n,1);
}
int main()
{
scanf("%lld%lld",&L,&R);Sqr=std::sqrt(R)+1;
for(re int i=2;i<=Sqr;i++) {
if(!f[i]) p[++tot]=i;
for(re int j=1;j<=tot&&p[j]*i<=Sqr;j++) {
f[p[j]*i]=1;if(i%p[j]==0) break;
}
}
printf("%lld\n",calc(R)-calc(L-1));
return 0;
}