第一次在uoj上交题？
把题面翻译成人话：求$[l,r]$中所有数的可重次大质因子之和。
设$i$的次大质因子为$f(i)$。$f(i)$虽然不积性，但还是可以考虑$min\_25$筛的思想。
设$S(n,k)=\sum\limits_{i=1}^n[minp(i)>P_k]f(i)$，答案就是$S(r,0)-S(l-1,0)$。
因为质数和$1$的$f$都是$0$，所以只需要考虑合数的贡献，枚举最小质因子及其次数$P_i^j$。$P_i^j$有两种贡献：
- $P_i$就是次小质因子：此时因子中除了$P_i^j$，就只会有一个大于$P_i$的质数$P_x$且$P_i^jP_x\le n$，也就是$\max\left\{g_0(\dfrac{n}{P_i^j},+\infty)-i,0\right\}$。而如果$j>1$，还要算上$P_i^j$自己。这部分贡献就是$P_i\times\left(\max\left\{g_0(\dfrac{n}{P_i^j},+\infty)-i,0\right\}+[j>1]\right)$
- $P_i$不是次小质因子：这部分就和$P_i$没啥关系了，因为最小质因子为$P_i^j$，次小质因子一定在上面，贡献为$S(\dfrac{n}{P_i^j},i)$
综上，$S(n,k)=\sum\limits_{i>k,P_i^2\le n,P_i^j\le n}P_i\times\left(\max\left\{g_0(\dfrac{n}{P_i^j},+\infty)-i,0\right\}+[j>1]\right)+S(\dfrac{n}{P_i^j},i)$
而且因为只需要考虑合数，当$P_k^2>n$的时候就可以返回$0$了。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 400005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
long long n,g[maxn<<1];
int prime[maxn>>2],sq,cnt;
bool is[maxn];
inline int id(long long x){return x<=sq?x:sq+n/x;}
long long S(long long n,int k){
if(1ll*prime[k]*prime[k]>n)return 0;
long long ans=0;
for(register int i=k+1;i<=cnt&&1ll*prime[i]*prime[i]<=n;++i){
long long base=prime[i];
for(register int j=1;base<=n;++j,base*=prime[i])
ans+=(max(g[id(n/base)]-i,0ll)+(j>1))*prime[i]+S(n/base,i);
}
return ans;
}
long long solve(long long N){
n=N,sq=sqrt(n);
for(long long l=1;l<=n;l=n/(n/l)+1)g[id(n/l)]=n/l-1;
for(register int i=1;i<=cnt;++i)
for(long long l=1;1ll*prime[i]*prime[i]<=n/l;l=n/(n/l)+1){
int k=id(n/l);
g[k]-=g[id(n/l/prime[i])]-i+1;
}
return S(n,0);
}
int main(){
for(register int i=2;i<maxn;++i){
if(!is[i])prime[++cnt]=i;
for(register int j=1;j<=cnt&&i*prime[j]<maxn;++j){
is[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
long long l=read<long long>(),r=read<long long>();
printf("%lld\n",solve(r)-solve(l-1));
}
