考虑min_25筛法实际执行的第一步,筛质数点值之和,这一步中减去合数的贡献总是在用它的最小质因子。而一个合数的最大真因子实际上就是它本身除掉它的最小质因子。
直接在min_25执行过程中统计一下答案就行了。
代码:
#include<bits/stdc++.h>#definelllonglong#definereregister#definecsconstcsintN=1e5+7;inlinellC(lln){return(n&1)?(n+1)/2*n:n/2*(n+1);}lll,r;intlim;llf1[N],f2[N];llcalc(lln){if(n<=1)return0;lim=sqrt(n);llans=0;for(intrei=1;i<=lim;++i)f1[i]=C(i)-1,f2[i]=C(n/i)-1;for(intrep=2;p<=lim;++p)if(f1[p]!=f1[p-1]){llt=f1[p-1],pre=f2[1];for(intrei=1,li=lim/p;i<=li;++i)f2[i]-=(f2[i*p]-t)*p;for(intrei=lim/p+1,li=std::min<ll>(n/p/p,lim);i<=li;++i)f2[i]-=(f1[n/i/p]-t)*p;if((ll)p*p<=lim)for(intrei=lim,li=p*p;i>=li;--i)f1[i]-=(f1[i/p]-t)*p;ans+=(pre-f2[1])/p;}returnans;}signedmain(){std::cin>>l>>r;std::cout<<calc(r)-calc(l-1)<<"\n";return0;}