題意：設$f(i)$表示$i$的不嚴格次大質因子（沒有為$0$），求${\sum }_{i=l}^{r}f(i)$

$l\le r\le 10^{11}$

這種和質因數有關的奇奇怪怪的函數的前綴和可以試試魔改min_25篩

設

$$S(n,j)=\sum _{i=2}^n[minp(i)>p_j]f(i)$$

枚舉最小的質因子$p_k$以及次數$e$

如果$p_k$不是次大質因子，直接遞歸到$S(?\frac{n}{p_k^e}?,k)$

否則考慮$p_k$的貢獻

如果是嚴格次大，那么枚舉最大的質因子

否則就是$[e>1]$

$$S(n,j)=\sum _{k=j+1}^{p_k\le \sqrt{n}}\sum _{e=1}^{p_k^e\le n}(S(?\frac{n}{p_k^e}?,k)+\sum _{i=p_k+1}^{?\frac{n}{p_k^e}?}[i\in prime]+[e>1])$$

注意$p_k+1$可能大于$?\frac{n}{p_k^e}?$，要特判一下

然后用min_25的方法預處理出質數個數的前綴和即可

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <cmath> #define MAXN 1000005 using namespace std; const int N=1e6; int np[MAXN],pl[MAXN],cnt; void init() {np[1]=1;for (int i=2;i<=N;i++){if (!np[i]) pl[++cnt]=i;for (int j=1,x;(x=i*pl[j])<=N;j++){np[x]=1;if (i%pl[j]==0) break;}} } typedef long long ll; ll val[MAXN],n,m; int key[MAXN],yek[MAXN],tot; inline int getkey(ll x){return x<=m? key[x]:yek[n/x];} ll g[MAXN]; ll S(ll n,int j) {if ((ll)pl[j]*pl[j]>n) return 0;ll sum=0;for (int k=j+1;(ll)pl[k]*pl[k]<=n&&k<=cnt;k++)for (ll e=1,v=pl[k];v<=n;e++,v*=pl[k])sum+=S(n/v,k)+pl[k]*(max(0ll,g[getkey(n/v)]-k)+(e>1));return sum; } ll solve(ll N) {m=sqrt(n=N);tot=0;for (ll l=1,r;l<=n;l=r+1){r=n/(n/l);val[++tot]=n/l;if (val[tot]<=m) key[val[tot]]=tot;else yek[n/val[tot]]=tot;}for (int i=1;i<=tot;i++) g[i]=val[i]-1;for (int j=1;j<=cnt;j++)for (int i=1;(ll)pl[j]*pl[j]<=val[i];i++)g[i]-=g[getkey(val[i]/pl[j])]-j+1;return S(n,0); } int main() {init();ll l,r;cin>>l>>r;cout<<solve(r)-solve(l-1);return 0; }

總結

以上是生活随笔為你收集整理的【UOJ188】 Sanrd【类min_25筛】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。