min_25筛
求(ans=sum_{i=1}^nf(i),nin[1,1e10])
满足：
- (f(p))是关于p的多项式
- (f(p^c))快速求得（通常是(O(1))）
- (f(n))为积性函数
时间复杂度(O(frac{n^{frac34}}{logn}))
预处理
[g(n,j)=sum_{i=1}^n[iin P||minp(i)>p_j]f`(i)
]
初始值(g(n,0))是把所有数当成质数的函数和（此时的(f`(i))已被拆成完全积性函数）
求
[g(n,|P|)=sum_{i=1}^n[iin P]f`(i)
]
考虑埃氏筛的过程，每次把最小质因子为(p_j)的筛去
转移
[g(n,j)=g(n,j-1),p_j^2>n
]
[g(n,j)=g(n,j-1)-f`(p_j)(g(lfloorfrac n {p_j}
floor,j-1)-sum_{i=1}^{j-1}[iin P]f`(i)),p_j^2<=n
]
但这样是(O(n|P|))的，考虑优化，发现n的取值只有(sqrt n)种，于是“手动”离散化，第二维可滚动掉，时间(O(sqrt n|P|))，空间(O(sqrt n))
计算答案
[s(n,j)=sum_{i=1}^n[minp(i)ge P_j]f(i)
]
[ans=s(n,1)
]
转移：(分质数和合数，合数部分枚举最小质因子及其次数)
[s(n,j)=g(n,|P|)-sum_{i=1}^{j-1}f(p_i)+sum_{p_kleq sqrt x,kge j}sum_{e>0,p_k^eleq n}f(p_k^e)(s(lfloorfrac n{p_k^e}
floor,k+1)+[e>1])
]
采用递归方式计算
注意：1不是质数也不是合数，最后要加上
例：LOJ6053简单的函数
求(ans=sum_{i=1}^nf(i)\%1000000007,nin[1,1e10])
性质：
- (f(1)=1)
- (f(p^c)=poplus c)
- (f(ab)=f(a)f(b),gcd(a,b)=1)
SOL：
除2外的质数(f(p)=p-1)拆成(f_1(p)=p,f_2(p)=1)
对应求出(g(n,j),h(n,j))
初值
[s(n,j)=g(n,|P|)-h(n,|P|)-sum_{i=1}^{j-1}f(p)
]
注意：2要特判一下
CODE：
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=250004,mod=1e9+7,inv2=5e8+4;
int n,sq,tot,m,h[N],g[N],sp[N],b[N],pri[N],id1[N],id2[N],w[N];
inline void pre(int mx){
for(int i=2;i<=mx;i++){
if(!b[i]){pri[++tot]=i;sp[tot]=sp[tot-1]+i;}
for(int j=1;j<=tot&&pri[j]*i<=mx;j++){
b[pri[j]*i]=1;
if(i%pri[j]==0)break;
}
}
}
int S(int x,int y){
if(x<=1||pri[y]>x)return 0;
int k=(x<=sq)?id1[x]:id2[n/x],ret=(g[k]-h[k]-sp[y-1]+y-1)%mod;
if(y==1)ret+=2;
for(int i=y,t1,t2;i<=tot&&pri[i]*pri[i]<=x;i++){
t1=pri[i];t2=pri[i]*pri[i];
for(int j=1;t2<=x;j++,t1=t2,t2*=pri[i])
(ret+=S(x/t1,i+1)*(pri[i]^j)%mod+(pri[i]^(j+1)))%=mod;
}
return ret;
}
signed main(){
n=read();sq=sqrt(n);
pre(sq);
for(int i=1,j;i<=n;i=j+1){
j=n/(n/i);
w[++m]=n/i;//手动离散化
g[m]=(w[m]%mod)*(w[m]%mod+1)%mod*inv2%mod-1;//f1(x)=x
h[m]=(w[m]-1)%mod;//f2(x)=1 拆成积性函数
if(w[m]<=sq)id1[w[m]]=m;
else id2[j]=m;
}
for(int j=1,k;j<=tot;j++)
for(int i=1;i<=m&&pri[j]*pri[j]<=w[i];i++){
k=(w[i]/pri[j]<=sq)?id1[w[i]/pri[j]]:id2[n/(w[i]/pri[j])];
(g[i]-=pri[j]*(g[k]-sp[j-1]))%=mod;
(h[i]-=h[k]-j+1)%=mod;
}
cout<<(S(n,1)+1+mod)%mod;
return (0-0);
}