P5325-[模板]Min_25筛
正題
題目鏈接:https://www.luogu.com.cn/problem/P5325
題目大意
定義一個積性函數滿足f(pk)=pk(pk?1)f(p^k)=p^k(p^k-1)f(pk)=pk(pk?1)
求∑i=1nf(i)\sum_{i=1}^nf(i)∑i=1n?f(i)
解題思路
首先我們可以把f(pk)f(p^k)f(pk)是質數的情況拆成一個222階的多項式f(x)=x2?xf(x)=x^2-xf(x)=x2?x。
然后就是Min25\text{Min25}Min25篩了。我們先需要求出質數有關的答案,考慮把這個多項式的多個階分開來求。
有關質數的求法,我們定義dpdpdp數組
gk(n,j)=∑i=1n[i∈Priorminp(i)>pj]ikg_k(n,j)=\sum_{i=1}^n[i\in Pri\ \ or\ \ minp(i)>p_j]i^kgk?(n,j)=i=1∑n?[i∈Pri??or??minp(i)>pj?]ik(上面PriPriPri表示質數集,minp(x)minp(x)minp(x)表示xxx的最小質因子,pjp_jpj?表示≤n\leq \sqrt{n}≤n?的第jjj個質因子,kkk表示多項式的某個階,后面為了方便gkg_kgk?寫作ggg,后文中的g(n,j)g(n,j)g(n,j)中的nnn都與輸入的nnn無關,只是一個變量)
具體的說就是如果iii是質數或者最小質因子超過pjp_jpj?,那當某個pjp_jpj?最接近但小于n\sqrt nn?時,g(n,j)g(n,j)g(n,j)就是我們需要的答案了。
因為一個合數xxx滿足minp(x)≤xminp(x)\leq\sqrt xminp(x)≤x?,所以pjp_jpj?的數量級很小,可以利用這個性質。
遞推這個數組時對于每次jjj往上加相當于多加上了一些限制條件,也就是g(n,j)g(n,j)g(n,j)相對于g(n,j?1)g(n,j-1)g(n,j?1)我們需要減去一些多余的答案。
這些多余的答案就是最小質因數是pjp_jpj?的數,這些數就是pjk?(g(npj,j?1)?g(pj?1,j?1))p_j^k*{\large(}\ g(\frac{n}{p_j},j-1)-g(p_{j-1},j-1)\ {\large)}pjk??(?g(pj?n?,j?1)?g(pj?1?,j?1)?)。
g(npj,j?1)?g(pj?1,j?1))g(\frac{n}{p_j},j-1)-g(p_{j-1},j-1)\ {\large)}g(pj?n?,j?1)?g(pj?1?,j?1)?)表示枚舉一個乘上pjp_{j}pj?之后不會超過nnn且最小質因子超過pjp_{j}pj?的數,這些數乘上pjp_jpj?后就是不重不漏的表示最小質因子是pjp_jpj?的數,因為y=xky=x^ky=xk是一個完全積性函數,所以可以直接乘上一個pjkp_j^kpjk?。
現在我們就有遞推式
g(n,j)=g(n,j?1)+pjk(g(npj,j?1)?g(pj?1,j?1))g(n,j)=g(n,j-1)+p_j^k{\large(}\ g(\frac{n}{p_j},j-1)-g(p_{j-1},j-1)\ {\large)}g(n,j)=g(n,j?1)+pjk?(?g(pj?n?,j?1)?g(pj?1?,j?1)?)
快速處理g(n,0)g(n,0)g(n,0)然后遞推,可以注意到g(pj?1,j?1)g(p_{j-1},j-1)g(pj?1?,j?1)就是前j?1j-1j?1個質數的kkk次方和,因為pjp_jpj?數量級只有n\sqrt nn?所以可以直接預處理,因為后面還要用就定義spi=∑i=1nf(pi)sp_i=\sum_{i=1}^nf(p_i)spi?=∑i=1n?f(pi?)
還有發現無論如何每個g(x,j)g(x,j)g(x,j)的取值都只與?nx?\lfloor\frac{n}{x}\rfloor?xn??有關,所以我們對于ggg數組的每一個jjj都只有n\sqrt nn?個連續的范圍內的同一取值。所以我們可以直接整除分塊來大大縮減數量級的空間和時間。
給出一個xxx如何快速得到g(x,j)g(x,j)g(x,j)的儲存地址?一個比較巧妙的方法是如果x≤nx\leq \sqrt nx≤n?那么ind1xind1_xind1x?表示xxx的儲存位置,否則用ind2nxind2_{\frac{n}{x}}ind2xn??表示xxx的儲存地址。
然后jjj那個維度我們只需要用到j=cntj=cntj=cnt(cntcntcnt表示n\sqrt nn?以內的質數數量)值,所以我們直接滾動來遞推就好了。
現在我們知道了所有的g(i,cnt)g(i,cnt)g(i,cnt),這道題的話具體的值就是g2(i,cnt)?g1(i,cnt)g_2(i,cnt)-g_1(i,cnt)g2?(i,cnt)?g1?(i,cnt)就可以表示前綴質數fff的函數和了。下面簡寫g(i)=g2(i,cnt)?g1(i,cnt)g(i)=g_2(i,cnt)-g_1(i,cnt)g(i)=g2?(i,cnt)?g1?(i,cnt)。
然后就是要求答案了,同樣使用dpdpdp的技巧,設
S(n,j)=∑i=2n[minp(i)>pj]f(i)S(n,j)=\sum_{i=2}^n[minp(i)>p_j]f(i)S(n,j)=i=2∑n?[minp(i)>pj?]f(i)
然后對于S(n,j)S(n,j)S(n,j)的答案我們可以分為質數和非質數兩部分,質數部分顯然就是g(n)?spng(n)-sp_ng(n)?spn?(不記得spspsp的去看前面定義)。
然后合數部分我們考慮遞歸下去處理就是∑k>jpke≤nf(pke)(S(npke,k)+[e≠1])\sum_{k>j}^{p_{k}^e\leq n}f(p_k^e){\large(}S(\frac{n}{p_k^e},k)+[e\neq1]{\large)}∑k>jpke?≤n?f(pke?)(S(pke?n?,k)+[e?=1])。pkep_k^epke?是枚舉質因子就不多說了,那個[e≠1][e\neq 1][e?=1]是因為pkp_kpk?已經作為質數被計算過了,但是后面的pkep_k^epke?還沒有。
現在就有S(n,j)S(n,j)S(n,j)的遞推式了
S(n,j)=g(n)?spn+∑k>jpke≤nf(pke)(S(npke,k)+[e≠1])S(n,j)=g(n)-sp_n+\sum_{k>j}^{p_{k}^e\leq n}f(p_k^e){\large(}S(\frac{n}{p_k^e},k)+[e\neq1]{\large)}S(n,j)=g(n)?spn?+k>j∑pke?≤n?f(pke?)(S(pke?n?,k)+[e?=1])
遞歸下去做就好了,說是不知道因為啥定理所以是不用記憶化的。
一個細節就是f(1)f(1)f(1)最好不要統計進去,最好加上就好了
據說時間復雜度是O(n34log?n)O(\frac{n^{\frac{3}{4}}}{\log n})O(lognn43??)的,反正這題我沒開O2O2O2的話1e101e101e10只跑了七百多毫秒。
code
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long using namespace std; const ll N=1e6+10,P=1e9+7; ll n,T,cnt,tot,pri[N],sp1[N],sp2[N],ind1[N],ind2[N],g1[N],g2[N],w[N]; bool v[N]; void init(ll n){for(ll i=2;i<=n;i++){if(!v[i]){pri[++cnt]=i;sp1[cnt]=(sp1[cnt-1]+i)%P;sp2[cnt]=(sp2[cnt-1]+i*i)%P;}for(ll j=1;j<=cnt&&i*pri[j]<=n;j++){v[i*pri[j]]=1;if(i%pri[j]==0)break;}}return; } ll S(ll x,ll y){if(pri[y]>=x)return 0;ll pos=(x>T)?ind2[n/x]:ind1[x];ll ans=g2[pos]-g1[pos]-(sp2[y]-sp1[y]);ans=(ans%P+P)%P;for(ll i=y+1;i<=cnt&&pri[i]*pri[i]<=x;i++){for(ll j=1,p=pri[i];p<=x;j++,p=p*pri[i]){ll w=p%P;(ans+=w*(w-1)%P*(S(x/p,i)+(j!=1))%P)%=P;}}return ans; } signed main() {scanf("%lld",&n);T=sqrt(n);init(T);ll inv2=(P+1)/2,inv6=(P+1)/6;for(ll l=1,r;l<=n;l=r+1){ll x=n/l;r=n/(n/l);w[++tot]=n/l;x%=P;g1[tot]=x*(x+1)%P*inv2%P-1;g2[tot]=x*(x+1)%P*(2*x+1)%P*inv6%P-1;if(n/l<=T)ind1[n/l]=tot;else ind2[n/(n/l)]=tot;}for(ll i=1;i<=cnt;i++)for(ll j=1;j<=tot&&pri[i]*pri[i]<=w[j];j++){ll k=(w[j]/pri[i]);k=(k>T)?ind2[n/k]:ind1[k];(g1[j]+=P-pri[i]*(g1[k]-sp1[i-1])%P)%=P;(g2[j]+=P-pri[i]*pri[i]%P*(g2[k]-sp2[i-1])%P)%=P;}printf("%lld\n",(S(n,0)+1)%P);return 0; }總結
以上是生活随笔為你收集整理的P5325-[模板]Min_25筛的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 作为曾经联想一员联想曾经的人才
- 下一篇: 三根线的路由器怎样设置家里三个路由器怎么