【UOJ#188】Sanrd（min_25篩）

題面

UOJ

題解

今天菊開講的題目。(千古神犇陳菊開，撲通撲通跪下來)
題目要求的就是所有數(shù)的次大質(zhì)因子的和。
這個(gè)部分和\(min\_25\)篩中枚舉最小值因子有異曲同工之妙。
min_25篩什么的戳這里
并且這題并沒有積性函數(shù)。
所以我們先篩出質(zhì)數(shù)個(gè)數(shù)。
然后考慮如何計(jì)算答案\(S(n,1)\)
首先看初值，假設(shè)當(dāng)前計(jì)算的是\(S(x,y)\)
表示的是\([1,x]\)中，所有最小質(zhì)因子大于等于\(Prime_y\)的貢獻(xiàn)
所有質(zhì)數(shù)的貢獻(xiàn)顯然是\(0\)，我們考慮計(jì)算合數(shù)的答案。
枚舉最小質(zhì)因子以及這個(gè)質(zhì)因子的次冪，在只剩下兩個(gè)質(zhì)因子的時(shí)候統(tǒng)計(jì)答案。
既然只剩下兩個(gè)質(zhì)因子，那么需要計(jì)算的就是\(x\)中所有大于等于\(Prime_y\)的質(zhì)數(shù)。
因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(S(x,y)\)一定右\(S(?,y-1)\)轉(zhuǎn)移過來
那么它的次小質(zhì)因子就是\(Prime_{y-1}\)，直接計(jì)算即可。
還需要額外考慮\(p^k\)的貢獻(xiàn)就是\(p\)

#include<iostream> #include<cmath> using namespace std; #define ll long long #define MAX 1000000 ll L,R,ans,w[MAX],g[MAX],Sqr; int id1[MAX],id2[MAX],m,pri[MAX],tot; bool zs[MAX]; void pre(int n) {for(int i=2;i<=n;++i){if(!zs[i])pri[++tot]=i;for(int j=1;j<=tot&&i*pri[j]<=n;++j){zs[i*pri[j]]=true;if(i%pri[j]==0)break;}} } ll S(ll n,ll x,int y) {if(x<=1||pri[y]>x)return 0;int k=(x<=Sqr)?id1[x]:id2[n/x];ll ret=1ll*pri[y-1]*(g[k]-y+1);for(int i=y;i<=tot&&1ll*pri[i]*pri[i]<=x;++i){ll p1=pri[i],p2=1ll*pri[i]*pri[i];for(int e=1;p2<=x;++e,p1=p2,p2*=pri[i])ret+=S(n,x/p1,i+1)+pri[i];}return ret; } ll Solve(ll n) {tot=m=0;pre(Sqr=sqrt(n));for(ll i=1,j;i<=n;i=j+1){j=n/(n/i);w[++m]=n/i;g[m]=w[m]-1;if(w[m]<=Sqr)id1[w[m]]=m;else id2[j]=m;}for(int j=1;j<=tot;++j)for(int i=1;i<=m&&1ll*pri[j]*pri[j]<=w[i];++i){int k=(w[i]/pri[j]<=Sqr)?id1[w[i]/pri[j]]:id2[n/(w[i]/pri[j])];g[i]-=g[k]-j+1;}return S(n,n,1); } int main() {cin>>L>>R;cout<<Solve(R)-Solve(L-1)<<endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/cjyyb/p/9269389.html

總結(jié)

以上是生活随笔為你收集整理的【UOJ#188】Sanrd（min_25筛）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。