LOj 2000「SDOI2017」数字表格（莫比乌斯反演）

柔光的暖阳◎ 2022-06-10 04:17 198阅读 0赞

题目链接：  
[LOj 2000][]

题意：  
给你 n 和 m。  
让你求 ans(n,m)=∏ni=1∏mj=1fib\[gcd(i,j)\]。

题解：

因为要求：ans(n,m)=∏ni=1∏mj=1fib\[gcd(i,j)\]  
枚举k=gcd(i,j),得:

### ans(n,m)=∏min(n,m)k=1fib\[k\]∑⌊nk⌋i=1∑⌊mk⌋j=1\[gcd(i,j)=1\]。 ###

其中\[gcd(i,j)=1\]表示若gcd(i,j)=1，该式值为1，否则为0。  
利用莫比乌斯函数的性质，得到：

### ans(n,m)=∏min(n,m)k=1fib\[k\]∑⌊nk⌋i=1∑⌊mk⌋j=1∑d|gcd(i,j)μ(d)。 ###

对每个 d 统计μ(d)被算了几次，则：

### ans(n,m)=∏min(n,m)k=1fib\[k\]∑⌊min(n,m)k⌋d=1⌊nkd⌋⌊mkd⌋μ(d)。 ###

如果我们直接算这个，复杂度是 O((n\+m)34)。会TLE。但也会有60分吧。  
我们可以令 p=kd ，则：

### ans(n,m)=∏min(n,m)p=1∏k|pfib\[k\]⌊np⌋⌊mp⌋μ(pk) ###

### =∏min(n,m)p=1(∏k|pfib\[k\]μ(pk))⌊np⌋⌊mp⌋。 ###

（如果做得多了，其实可以直接推出上式，都是套路了。)  
令g(x)=∏k|pfib\[k\]μ(pk)，可以通过枚举d，对于每个满足k|p 的 g(p)都乘上fib\[k\]μ(pk)，只需提前预处理μ(x)、fib(x)和fib(x)的逆元即可。  
可以发现，发现对于每个p，∏k|pfib\[k\]μ(pk) 的值是固定的，而与n和m无关，于是我们先用筛法预处理出每个p对应的这个式子的值，前缀积一下，利用⌊np⌋⌊mp⌋ 只有 O(n√\+m−−√) 种取值。我们可以在O((n\+m)log(mod))时间内计算并回答每次询问（其中log(mod)为快速幂）,总的时间负责度就是O((max(n,m)\+T(n√\+m−−√))log(mod))。

### 注意： ###

#### 快速幂求答案的时候指数模一下mod−1。因为 a(p−1)=1(modp)p，p 是质数,所以所有的指数是对(p−1)取模的。如果这个点不注意，100分会卡成30分… ####

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1000010;
    const int mod = 1e9+7; 
    int tot=0;
    int check[N],mu[N],fib[N];
    int prime[N];
    int inv[N];
    int g[N],f[N];
    ll q_mod(ll a,ll b)
    {
        ll res = 1;
        while(b)
        {
            if(b&1) res=res*a%mod;
            b>>=1;
            a=a*a%mod;
        }
        return res;
    }
    void mobius()
    {
        mu[1]=1;
        int n=1000005;
        for(int i=2;i<=n;i++)
        {
            if(!check[i]){
                prime[++tot]=i;
                mu[i]=-1;
            }
            for(int j=1;j<=tot&&i*prime[j]<=n;j++)
            {
                check[i*prime[j]]=1;
                if(!(i%prime[j]))
                {   
                    mu[i*prime[j]]=0;
                    break;
                }
                else mu[i*prime[j]]=-mu[i];
            }
        }
    
    
        for(int i=0;i<=n;i++){
            f[i]=g[i]=1;
        }
        fib[0]=0; fib[1]=1;
        for(int i=2;i<=n;i++)
        {
            fib[i]=fib[i-1]+fib[i-2];
            if(fib[i]>=mod) fib[i]-=mod;
        }
    
        for(int i=2;i<=n;i++){
            inv[i]=q_mod(fib[i],mod-2);
        }
        for(int i=3;i<=n;i++)
        {
            for(int j=i,k=1;j<=n;j+=i,k++)
            {
                if(mu[k]==1)
                {
                    f[ j ] = 1LL * f[ j ] * fib[ i ] % mod;
                    g[ j ] = 1LL * g[ j ] * inv[ i ] % mod;
                }
                else if(mu[k]==-1)
                {
                    f[ j ] = 1LL * f[ j ] * inv[ i ] % mod;
                    g[ j ] = 1LL * g[ j ] * fib[ i ] % mod;
                }
            }
        }
        for(int i=2;i<=n;i++){
            f[i] = 1LL * f[i] * f[i-1] % mod;
            g[i] = 1LL * g[i] * g[i-1] % mod;
        }
    }
    int t,n,m;
    int solve()
    {
        int ans = 1 ;
        for(int pos,i=1;i<=n;i=pos+1)
        {
            pos = min(n/(n/i),m/(m/i));
            ans = 1LL * ans * q_mod( 1LL * f[pos] * g[i-1] % mod,1LL * (n/i) * (m/i) % (mod-1)) % mod;
        }
        //cout<<"ans="<<ans<<endl; 
        return ans;
    }
    
    int main()
    {
    //  freopen("product5.in","r",stdin);
        mobius();
    //  cout<<"init finish"<<endl;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            if(n>m)swap(n,m);
            int ans = solve();
            printf("%d\n",ans);
        }
        return 0;
    }

[LOj 2000]: https://loj.ac/problem/2000