題面

傳送門

題解

這是一道語文題

不難看出，題目所求即為\(l\)到\(r\)中每個數的次大質因子

我們考慮\(Min\_25\)篩的過程，設

\[S(n,j)=\sum_{i=1}^nsec_p(i)[min_p(i)\geq P_j]\]

用人話來說的話，就是\(S(n,j)\)表示\(1\)到\(n\)之間所有滿足最小值因子大于等于\(P_j\)的\(i\)的次大質因子之和

我們照例把質數和合數的貢獻分開考慮。所有質數貢獻為\(0\)，而對于合數，我們枚舉最小質因子\(P_k\)。此時分為兩種情況，如果\(P_k\)不是次大質因子，那么\(S(n,j)\)要加上所有滿足\(k>j\)的\(S(\left\lfloor\frac{n}{{P_k}^e}\right\rfloor,k+1)\)。如果\(P_k\)是次大質因子，那么剩下的數肯定是一個大于等于\(P_k\)的質因子，也就是\(P_k\)到\(\left\lfloor\frac{n}{{P_k}^e}\right\rfloor\)之間質數的個數

用從隔壁大佬那里偷來的公式來寫的話就是這樣子

\[S(n,j)=\sum_{k\ge j}\sum_{e=1}^{p_k^{e+1}\le n}S(\lfloor\frac{n}{p^{e}_k}\rfloor,k+1)+p_k\sum_{i=p_k}^{\lfloor\frac{n}{p^{e}_k}\rfloor}[i\in P]\]

//minamoto #include<bits/stdc++.h> #define R register #define ll long long #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; const int N=1e6+5; int p[N],id1[N],id2[N],m,tot,sqr;bitset<N>vis; ll l,r,qwq,w[N],g[N]; void init(int n){fp(i,2,n){if(!vis[i])p[++tot]=i;for(R int j=1;j<=tot&&1ll*i*p[j]<=n;++j){vis[i*p[j]]=1;if(i%p[j]==0)break;}} } ll S(ll n,int m){if(n<=2||p[m]>n)return 0;ll res=0;for(R int i=m;i<=tot&&1ll*p[i]*p[i]<=n;++i)for(R ll tmp=p[i];tmp*p[i]<=n;tmp*=p[i]){int k=(n/tmp<=sqr)?id1[n/tmp]:id2[qwq/(n/tmp)];res+=S(n/tmp,i+1)+(g[k]-i+1)*p[i];}return res; } ll calc(ll n){qwq=n,m=0;for(R ll i=1,j;i<=n;i=j+1){j=n/(n/i),w[++m]=n/i;w[m]<=sqr?id1[w[m]]=m:id2[n/w[m]]=m;g[m]=w[m]-1;}fp(j,1,tot)for(R int i=1;1ll*p[j]*p[j]<=w[i];++i){int k=(w[i]/p[j]<=sqr)?id1[w[i]/p[j]]:id2[n/(w[i]/p[j])];g[i]=g[i]-g[k]+j-1;}return S(n,1); } int main(){ // freopen("testdata.in","r",stdin);scanf("%lld%lld",&l,&r),init(sqr=sqrt(r));printf("%lld\n",calc(r)-calc(l-1));return 0; }

轉載于:https://www.cnblogs.com/bztMinamoto/p/10415464.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的uoj#188. 【UR #13】Sanrd（Min_25筛）的全部內容，希望文章能夠幫你解決所遇到的問題。

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