正題

題目鏈接:https://www.luogu.com.cn/problem/P3704

---

題目大意

$T$組詢(xún)問(wèn)，給出$n,m$求$$\prod _{i=1}^n\prod _{j=1}^{m}Fb{i}_{gcd(i,j)}$$
其中$Fb{i}_x$表示第$x$項(xiàng)斐波那契數(shù)列。

---

解題思路

答案就是$$\prod _{x=1}^{n}Fb{i}_x^{{\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)==x]}$$
然后上反演就是$$\prod _{x=1}^{n}Fb{i}_x^{{\sum }_{x|d}?\frac{n}{d}??\frac{m}{d}?\mu (\frac{d}{x})}$$
同樣是提出來(lái)$$\prod _{d=1}^n(\prod _{x|d}^{n}Fb{i}_x^{\mu (\frac{d}{x})}{)}^{?\frac{n}{d}??\frac{m}{d}?}$$
然后預(yù)處理${\prod }_{x|d}^{n}Fb{i}_x^{\mu (\frac{d}{x})}$的前綴積再整除分塊即可

時(shí)間復(fù)雜度$O(T\sqrt{n+m})$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e6+10,P=1e9+7; ll T,n,m,cnt,ans;bool v[N]; ll mu[N],f[N],g[N],pri[N],inv[N]; 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; } void Prime(){mu[1]=f[1]=inv[1]=g[0]=g[1]=1;for(ll i=2;i<N;i++){if(!v[i])pri[++cnt]=i,mu[i]=-1;g[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]*mu[pri[j]];}}for(ll i=2;i<N;i++)f[i]=(f[i-1]+f[i-2])%P,inv[i]=power(f[i],P-2);for(ll i=1;i<N;i++){if(!mu[i])continue;for(ll j=i;j<N;j+=i){if(mu[i]==1)(g[j]*=f[j/i])%=P;else (g[j]*=inv[j/i])%=P;}}inv[1]=inv[0]=1;for(ll i=2;i<N;i++)g[i]=g[i]*g[i-1]%P,inv[i]=power(g[i],P-2);return; } int main() {Prime();scanf("%lld",&T);while(T--){scanf("%lld%lld",&n,&m);ans=1;if(n>m)swap(n,m);for(ll l=1,r;l<=n;l=r+1){r=min(n/(n/l),m/(m/l));ll mul=g[r]*inv[l-1]%P;ans=ans*power(mul,(n/l)*(m/l)%(P-1))%P;}printf("%lld\n",ans);} }

總結(jié)

以上是生活随笔為你收集整理的P3704-[SDOI2017]数字表格【莫比乌斯反演】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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