洛谷3704 [SDOI2017] 数字表格【莫比乌斯反演】

题目分析：

比较有意思，但是套路的数学题。

题目要求$ \prod_{i=1}^{n} \prod_{j=1}^{m}Fib(gcd(i,j)) $.

注意到$ gcd(i,j) $有大量重复，采用莫比乌斯反演。可以写成：

$ \prod_{i=1}^{min(n,m)}Fib(i)^{\sum_{i|d}\mu(\frac{d}{i})\lfloor \frac{n}{d}\rfloor\lfloor \frac{m}{d}\rfloor} $.

更进一步的，我们可以发现幂是一个求和，那么把求和依次提出，再重新组合在一起，就变成了：

$ \prod_{i=1}^{min(n,m)}(\prod_{i|d}Fib(i)^{\mu(\frac{d}{i})})^{\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor} $.

可以发现最外层的积的下标是$ i $或$ d $对答案没有影响，原因我们可以考虑当下标是$ i $的时候，它会对它的每个倍数产生影响，而倍数的影响是不论$ i $的。所以对于每个倍数我们同样可以枚举因数，式子可以写成：

$ \prod_{d=1}^{min(n,m)}(\prod_{i|d}Fib(i)^{\mu(\frac{d}{i})})^{\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor} $.

注意这个式子，它的里层是一个只与当前的$ d $有关的式子，而外层是一个典型的分块。那么我们预处理出里面的情况并做前缀积，外面再采用分块，这道题就可以顺利解决。

对于里面的式子，我们需要$ O(nlog{n}) $进行预处理，而每个询问我们可以分块解决，单次询问的时间复杂度是$ O(\sqrt{n}log{n}) $所以时间复杂度是$O(nlog{n}+T\sqrt{n}log{n})$.

注意到这题没有用到斐波那契数列的任何性质，所以函数$ Fib(x) $可以改成任意其它函数。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int mod = ;

 const int maxn = ;

 const int N = ;

 int n,m;

 int Fib[maxn],Inv[maxn];

 int MFib[maxn],MInv[maxn];

 int flag[maxn],prime[maxn>>],mu[maxn],num;

 int fast_pow(int now,long long pw){

     int z = now,ans = ;long long im = ;

     while(im <= pw){

     if(im & pw) ans = (1ll*ans*z)%mod;

     z = (1ll*z*z)%mod; im <<= ;

     }

     return ans;

 }

 void GetMiu(){

     flag[] = ;mu[] = ;

     for(int i=;i<=N;i++){

     if(!flag[i]) prime[++num] = i,mu[i] = -;

     for(int j=;j<=num&&i*prime[j]<=N;j++){

         flag[i*prime[j]] = ;

         if(i % prime[j] == ) {mu[i*prime[j]] = ;break;}

         else mu[i*prime[j]] = -mu[i];

     }

     }

 }

 void init(){

     GetMiu();

     Fib[] = ; Fib[] = ;

     for(int i=;i<=N;i++) Fib[i] = (Fib[i-]+Fib[i-])%mod;

     for(int i=;i<=N;i++) Inv[i] = fast_pow(Fib[i],mod-);

     for(int i=;i<=N;i++) MFib[i] = ;

     for(int i=;i<=N;i++){

     for(int j=;i*j<=N;j++){

         if(mu[j] == ) continue;

         if(mu[j] == ) MFib[i*j] = (1ll*MFib[i*j]*Fib[i])%mod;

         else MFib[i*j] = (1ll*MFib[i*j]*Inv[i])%mod;

     }

     }

     for(int i=;i<=N;i++) MFib[i] = (1ll*MFib[i]*MFib[i-])%mod;

     for(int i=;i<=N;i++) MInv[i] = fast_pow(MFib[i],mod-);

 }

 void work(){

     int res = ;

     for(int i=;i<=min(n,m);){

     int nxt = min(n/(n/i),m/(m/i));

     long long z1 = 1ll*(n/i)*(m/i);

     res = (1ll*res*fast_pow((1ll*MFib[nxt]*MInv[i-])%mod,z1))%mod;

     i = nxt+;

     }

     printf("%d\n",res);

 }

 int main(){

     init();

     int T; scanf("%d",&T);

     while(T--){

     scanf("%d%d",&n,&m);

     work();

     }

     return ;

 }

巴特西

洛谷3704 [SDOI2017] 数字表格【莫比乌斯反演】

最新文章

热门文章

巴特西

洛谷3704 [SDOI2017] 数字表格 【莫比乌斯反演】

最新文章

热门文章

洛谷3704 [SDOI2017] 数字表格【莫比乌斯反演】