正題

題目鏈接:https://ac.nowcoder.com/acm/contest/11174/F

---

題目大意

給出$n,k$求
$$\sum _{i_1=1}^n\sum _{i_2=1}^n...\sum _{i_k=1}^{n}gcd(f_{i_1},f_{i_2},...,f_{i_k})$$
對(duì)$10^9+9$取模

其中$f_i$表示斐波那契數(shù)列的第$i$項(xiàng)

$1\le n,k\le 10^8$

---

解題思路

看上去就很莫比烏斯反演，首先把$f$提出來然后直接上莫反就是
$$\sum _{i=1}^n{f}_i\sum _{j=1}^{?\frac{n}{i}?}\mu (j)?\frac{n}{ij}{?}^k$$
這個(gè)式子其實(shí)就可以直接做了，外面$f_i$是一個(gè)整除分塊，然后里面的式子也是一個(gè)整除分塊。需要的算法是一個(gè)矩陣乘法求斐波那契的前綴和（當(dāng)然因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$\sqrt{5}$在$10^9+9$下有二次剩余可以直接用特制方程求）還有一個(gè)杜教篩求$\mu$的前綴和。

因?yàn)檎謮K套整除分塊的復(fù)雜度是$O(n^{\frac{3}{4}})$，然后最里面套個(gè)杜教篩復(fù)雜度不會(huì)大很多所以能過。

然后有一個(gè)大佬的做法是把上面那個(gè)式子化一下
$$\sum _{i=1}^n?\frac{n}{i}{?}^k\sum _{d|i}{f}_d\mu (\frac{i}{d})$$
（相當(dāng)于外面枚舉$i\times j$然后枚舉它的約數(shù)）

然后因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$\mu ?I=?$，所以$f?\mu ?I=f??=f$。所以如果在能快速求$f$的前綴和的情況下求$f?\mu$的前綴和可以用杜教篩來做。

然后上面那個(gè)式子整除分塊一下就好了

代碼的寫法是第一種

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<map> #define ll long long using namespace std; const ll N=5e6+10,S=3,P=1e9+9; struct Matrix{ll a[S][S]; }c,f,am; ll n,k,ans,cnt,mu[N],pri[N/10]; bool v[N];map<ll ,ll >mp; Matrix operator*(Matrix &a,Matrix &b){memset(c.a,0,sizeof(c.a));for(ll i=0;i<S;i++)for(ll j=0;j<S;j++)for(ll k=0;k<S;k++)(c.a[i][j]+=a.a[i][k]*b.a[k][j]%P)%=P;return c; } ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } ll Fbi(ll b){memset(f.a,0,sizeof(f.a));am.a[0][0]=am.a[0][2]=0;am.a[0][1]=1;f.a[2][2]=1;f.a[0][1]=1;f.a[1][1]=1;f.a[1][0]=1;f.a[1][2]=1;while(b){if(b&1)am=am*f;f=f*f;b>>=1; }return am.a[0][2]; } void Prime(){mu[1]=1;for(ll i=2;i<N;i++){if(!v[i])pri[++cnt]=i,mu[i]=-1;for(ll j=1;j<=cnt&&i*pri[j]<N;j++){v[i*pri[j]]=1;if(i%pri[j]==0)break;mu[i*pri[j]]=-mu[i];}}for(ll i=1;i<N;i++)mu[i]+=mu[i-1];return; } ll GetMu(ll n){if(n<N)return mu[n];if(mp[n])return mp[n];ll ans=1;for(ll l=2,r;l<=n;l=r+1)r=n/(n/l),ans=ans-(r-l+1)*GetMu(n/l);return mp[n]=ans; } ll g(ll n){ll ans=0;for(ll l=1,r;l<=n;l=r+1){r=n/(n/l);ll tmp=GetMu(r)-GetMu(l-1);ans=(ans+tmp*power(n/l,k)%P)%P;}return ans; } signed main() {Prime();scanf("%lld%lld",&n,&k);for(ll l=1,r;l<=n;l=r+1){r=n/(n/l);ll tmp=Fbi(r)-Fbi(l-1);ans=(ans+tmp*g(n/l)%P)%P;}printf("%lld\n",(ans+P)%P);return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛84F-牛客推荐系统开发之下班【莫比乌斯反演,杜教筛】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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