[SDOI2017]数字表格-数论

【题目地址-IN-Luogu】

题意简述

我们定义$f$为斐波那契数列，那么$f(0)=0,f(1)=1,f(i)=f(i-1)+f(i-2)[i\ge 2]$

$T\le 1000$组询问，每次给定 n , m ≤ 1 0 6 n,m\leq 10^6 n,m≤106询问下面式子的值在模 1 0 9 + 7 10^9+7 109+7后的答案。

∏ i = 1 n ∏ j = 1 m f ( g c d ( i , j ) ) \prod_{i=1}^n\prod_{j=1}^mf(gcd(i,j)) i=1∏n​j=1∏m​f(gcd(i,j))

还是莫比乌斯反演的套路，虽然变成了累乘，但是做法还是类似的，我们枚举$gcd$，然后式子就可以变成（这里默认$n\le m$，不满足则交换）：

∏ d = 1 n f ( d ) ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = d ] \prod_{d=1}^nf(d)^{\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d]} d=1∏n​f(d)∑i=1n​∑j=1m​[gcd(i,j)=d]

这里相当于每一个$f(d)$都会被乘 ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = d ] \sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d] ∑i=1n​∑j=1m​[gcd(i,j)=d]次，$f(d)$可以$O(n)$预处理，主要是指数还不好处理，所以我们接下来对指数进行反演，可以得到：

∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ m d ⌋ [ g c d ( i , j ) = 1 ] = ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ m d ⌋ ∑ w ∣ i , w ∣ j μ ( w ) = ∑ w ∣ d μ ( d w ) ⌊ n d ⌋ ⌊ m d ⌋ \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1] \\=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{w|i,w|j}\mu(w) \\=\sum_{w|d}\mu(\frac{d}{w})\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor i=1∑⌊dn​⌋​j=1∑⌊dm​⌋​[gcd(i,j)=1]=i=1∑⌊dn​⌋​j=1∑⌊dm​⌋​w∣i,w∣j∑​μ(w)=w∣d∑​μ(wd​)⌊dn​⌋⌊dm​⌋

然后我们将其带回原式得到：

∏ d = 1 n f ( d ) ∑ w ∣ d μ ( d w ) ⌊ n d ⌋ ⌊ m d ⌋ \prod_{d=1}^nf(d)^{\sum_{w|d}\mu(\frac{d}{w})\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor} d=1∏n​f(d)∑w∣d​μ(wd​)⌊dn​⌋⌊dm​⌋

把上面的一个$\sum$拿下来，可以得到：

∏ d = 1 n ( ∏ w ∣ d f ( d ) μ ( d w ) ) ⌊ n d ⌋ ⌊ m d ⌋ \prod_{d=1}^n\left(\prod_{w|d}f(d)^{\mu(\frac{d}{w})}\right)^{\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor} d=1∏n​⎝⎛​w∣d∏​f(d)μ(wd​)⎠⎞​⌊dn​⌋⌊dm​⌋

然后我们可以$O(n(logn+快速幂))$的预处理 ( ∏ w ∣ d f ( d ) μ ( d w ) ) \left(\prod_{w|d}f(d)^{\mu(\frac{d}{w})}\right) (∏w∣d​f(d)μ(wd​))函数和其前缀积，然后对于外面的数论分块即可。而对于每次提取中间一段的乘积，我们用逆元将前面的除去即可。

复杂度 O ( n l o g n + T n ) O(nlogn+T\sqrt n) O(nlogn+Tn ​)

#include
#include
#include
#define ll long long
using namespace std;
const int M=1e6+10;
const ll Mod=1e9+7;
bool vis[M];
int n,m;
ll prime[M],f[M],F[M],mu[M],cnt,inv[M],MAX=1e6;
ll fpow(ll a,ll b){ll res=1;for(;b;b>>=1,a=(a*a)%Mod){if(b&1)res=(res*a)%Mod;}return res;
}
void init(){F[0]=mu[1]=F[1]=f[1]=inv[1]=1;inv[0]=mu[0]=1;for(int i=2;i<=MAX;i++){F[i]=1;f[i]=(f[i-1]+f[i-2])%Mod;inv[i]=fpow(f[i],Mod-2);if(!vis[i]){prime[++cnt]=i;mu[i]=-1;}for(int j=1,v;j<=cnt&&i*prime[j]<=MAX;j++){v=i*prime[j];vis[v]=1;if(!(i%prime[j])){break;}mu[v]=-mu[i];}}for(int i=1;i<=MAX;i++){if(!mu[i]) continue;for(int j=i;j<=MAX;j+=i){if(mu[i]==-1)F[j]=F[j]*inv[j/i]%Mod;else F[j]=F[j]*f[j/i]%Mod;}}for(int i=2;i<=MAX;i++)F[i]=(F[i]*F[i-1])%Mod;}
ll solve(){if(n>m)swap(n,m);ll ans=1;for(ll i=1,j;i<=n;i=j+1){j=min(n/(n/i),m/(m/i));ans=(ans*fpow((F[j]*fpow(F[i-1],Mod-2)%Mod)%Mod,1ll*(n/i)*(m/i)))%Mod;}return ans;
}
int T;
int main(){init();for(scanf("%d",&T);T--;){scanf("%d%d",&n,&m);printf("%lld\n",solve());}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！