令 ( s(n,j)=sumlimits_{i=1}^{n}[min_i>=p_j]f(j) ) ，其中 ( min_i ) 表示 i 的最小质因子。
令 ( g(n,j)=sumlimits_{i=1}^{n}[i in P or min_i>p_j]1 ) ，其中 P 表示质数集合。
( s(n,j)=s(n,j+1)+s(frac{n}{p_j},j)+p_j(g(frac{n}{p_j},cnt)-(j-1)) ) ，其中 cnt 表示 ( <=sqrt n ) 的最大质数。
( s(frac{n}{p_j},j) ) 表示除掉 ( p_j ) 后是合数的数的贡献， ( g(frac{n}{p_j},cnt)-(j-1) ) 表示除掉 ( p_j ) 后是一个 ( >=p_j ) 的质数的数的个数。
所以算 s 的时候要从小到大枚举 n 。如果每次从 m 开始枚举，在 n 较小的时候 continue 的话复杂度不对，但发现 j 是递减的，即 ( p_j ) 递减，所以每次最小的可行的 n 越来越小，用指针指一下就行了。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long using namespace std; const int N=640000; ll n,p2[N],w[N],s[N],g[N];int m,cnt,base,p[N];bool vis[N]; void init() { m=cnt=0;base=sqrt(n); for(ll i=1,j;i<=n;i=n/j+1)w[++m]=j=n/i; memset(vis,0,sizeof vis); for(int i=2;i<=base;i++) { if(!vis[i])p[++cnt]=i,p2[cnt]=(ll)i*i; for(int j=1,d;j<=cnt&&(d=i*p[j])<=base;j++) {vis[d]=1;if(i%p[j]==0)break;} } } int Id(ll x){return x<=base?m-x+1:n/x;} void cz() { for(int i=1;i<=m;i++)g[i]=w[i]-1; for(int j=1,pl=0;j<=cnt;j++,pl++)//pl=j-1 for(int i=1;i<=m&&p2[j]<=w[i];i++) g[i]-=g[Id(w[i]/p[j])]-pl; } ll solve() { init();cz();memset(s,0,sizeof s); int p0=1; for(int j=cnt;j;j--) { while(p0<=m&&p2[j]<=w[p0])p0++; for(int i=p0-1;i;i--) { int k=Id(w[i]/p[j]); s[i]+=s[k]+(ll)p[j]*(g[k]-(j-1)); } } return s[1]; } int main() { ll ans=0; scanf("%lld",&n);n--;if(n)ans=-solve(); scanf("%lld",&n);ans+=solve(); printf("%lld ",ans); return 0; }