分析
因为题目中所给函数(f(x))的前缀和无法较快得出，考虑打表以下两个函数：
[g(x)=x imes [x是质数]
]
[h(x)=1 imes [x是质数]
]
这两个函数的前缀和都可以通过Min_25筛第一阶段的处理得出，时间复杂度为(O(frac{n^{frac{3}{4}}}{log n}))。
我们发现：
[f(2)=g(2)+h(2)
]
[f(x)=g(x)-h(x),x是质数 且 x
eq 2
]
然后就可以把这两个函数一起做Min_25筛的第二阶段，(y=1)的时候特判一下加个(2)就好了，时间复杂度为(O(frac{n^{frac{3}{4}}}{log n}))。（太鶸了并不会证时间复杂度）
（还是写哈希表更直观，虽然也更慢）
代码
#include <bits/stdc++.h>
#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;
using std::cin;
using std::cout;
using std::endl;
inline LL read(){
LL x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const LL MAXN=1e10+5;
const int MOD=1e9+7;
const int INV2=5e8+4;
const int HASH=3e6-1;
const int MAXR=2e5+5;
LL n,num[MAXR];
int prm[MAXR],sum[MAXR],cnt;
int g0[MAXR],g1[MAXR],tot;
int id1[MAXR],id2[MAXR];
bool vis[MAXR];
void pre_process(int n){
rin(i,2,n){
if(!vis[i]) prm[++cnt]=i,sum[cnt]=(sum[cnt-1]+prm[cnt])%MOD;
rin(j,1,cnt){
if(i*prm[j]>n) break;
vis[i*prm[j]]=true;
if(i%prm[j]==0) break;
}
}
}
inline int getid(LL x){
if(x<=MAXR-5) return id1[x];
else return id2[n/x];
}
inline int min_25(LL x,int y){
if(x<2||x<prm[y]) return 0;
int xx=getid(x),ret=(((g1[xx]-sum[y-1])-(g0[xx]-(y-1)))%MOD+MOD)%MOD;
if(y==1) ret=(ret+2)%MOD;
rin(i,y,cnt){
if(1ll*prm[i]*prm[i]>x) break;
register LL now=prm[i];
for(register int j=1;now*prm[i]<=x;++j,now*=prm[i])
ret=(ret+1ll*(prm[i]^j)*min_25(x/now,i+1)+(prm[i]^(j+1)))%MOD;
}
return ret;
}
int main(){
n=read();pre_process((int)(sqrt(n)+0.5));
for(register LL i=1,nxti=0;i<=n;i=nxti+1){
num[++tot]=n/i,nxti=n/num[tot];
if(num[tot]<=MAXR-5) id1[num[tot]]=tot;
else id2[n/num[tot]]=tot;
g0[tot]=(num[tot]-1)%MOD;
g1[tot]=(2+num[tot])%MOD*((num[tot]-1)%MOD)%MOD*INV2%MOD;
}
rin(i,1,cnt){
rin(j,1,tot){// num[j] from big to small.
if(1ll*prm[i]*prm[i]>num[j]) break;
int k=getid(num[j]/prm[i]);
g0[j]=(g0[j]-(g0[k]-(i-1))+MOD)%MOD;
g1[j]=((g1[j]-1ll*prm[i]*(g1[k]-sum[i-1]))%MOD+MOD)%MOD;
}
}
printf("%d
",min_25(n,1)+1);
return 0;
}