BZOJ 4816 [Sdoi2017]数字表格 ——莫比乌斯反演

大力反演出奇迹。

然后xjb维护。

毕竟T1

#include <map>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
#define md 1000000007
#define maxn 1000005
 
int T,n,m,f[maxn],g[maxn],finv[maxn],ginv[maxn],mu[maxn];
int vis[maxn],pr[maxn],top=0;
 
int ksm(int a,int b)
{
    int ret=1;
    while (b)
    {
        if (b&1) ret=(ll)ret*a%md;
        a=(ll)a*a%md;
        b>>=1;
    }
    return ret;
}
 
void init()
{
    f[0]=0; f[1]=1; mu[1]=1; g[0]=1; g[1]=1;
    F(i,2,maxn-1)
    {
        f[i]=(f[i-1]+f[i-2])%md; finv[i]=ksm(f[i],md-2);
        g[i]=1;
        if (!vis[i]) pr[++top]=i,mu[i]=-1;
        for (int j=1;j<=top&&(ll)i*pr[j]<maxn;++j)
        {
            vis[i*pr[j]]=1;
            if (i%pr[j]==0) {mu[i*pr[j]]=0;break;}
            mu[i*pr[j]]=mu[i]*mu[pr[j]];
        }
    }
    F(i,2,maxn-1)
        for (int j=1;(int)i*j<maxn;++j)
        {
            int tmp;
            switch (mu[j])
            {
                case 1:tmp=f[i];break;
                case 0:tmp=1; break;
                case -1:tmp=finv[i];break;
            }
            g[i*j]=(ll)g[i*j]*tmp%md;
        }
    F(i,1,maxn-1) g[i]=(ll)g[i]*g[i-1]%md;
    F(i,0,maxn-1) ginv[i]=ksm(g[i],md-2);
}
 
int cal(int n,int m)
{
    int ans=1;
    for (int last=0,i=1;i<=n&&i<=m;i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        ans=(ll)ans*ksm((ll)g[last]*ginv[i-1]%md,(ll)(n/i)*(m/i)%(md-1))%md;
    }
    return ans;
}
 
int main()
{
    init(); scanf("%lld",&T);
    while (T--)
    {
        scanf("%lld%lld",&n,&m);
        printf("%lld
",cal(n,m));
    }
    return 0;
}