题目链接

题解

反演

∏T=1min⁡(n,m)(∏d∣Tfib(d)μ(d))⌊n/d⌋⌊m/d⌋ \prod_{T=1}^{\min(n,m)}(\prod_{d|T}fib(d)^{\mu(d)})^{\lfloor n/d\rfloor\lfloor m/d\rfloor} T=1∏min(n,m)​(d∣T∏​fib(d)μ(d))⌊n/d⌋⌊m/d⌋

预处理出中间部分，整除分块即可。

注意不要暴力算$fib(d)$的逆元，可以预处理出逆元。

代码

#include 
    
     #include 
     
      int read(){
      int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
          if(ch=='-')        {
              f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
          x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=1000000;const int mod=1000000007;const int pmod=mod-1;int quickpow(int a,int b){
      int res=1;  while(b)    {
          if(b&1)        {
              res=1ll*res*a%mod;        }      a=1ll*a*a%mod;      b>>=1;    }  return res;}int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10],f[maxn+10],fib[maxn+10],ifib[maxn+10];int getprime(){
      p[1]=mu[1]=1;  for(int i=2; i<=maxn; ++i)    {
          if(!p[i])        {
              prime[++cnt]=i;          mu[i]=-1;        }      for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)        {
              int x=i*prime[j];          p[x]=1;          if(i%prime[j]==0)            {
                  mu[x]=0;              break;            }          mu[x]=-mu[i];        }    }  fib[0]=ifib[0]=0;  fib[1]=ifib[1]=1;  for(int i=2; i<=maxn; ++i)    {
          fib[i]=fib[i-1]+fib[i-2];      if(fib[i]>=mod)        {
              fib[i]-=mod;        }      ifib[i]=quickpow(fib[i],mod-2);    }  for(int i=0; i<=maxn; ++i)    {
          f[i]=1;    }  for(int d=1; d<=maxn; ++d)    {
          for(int T=d; T<=maxn; T+=d)        {
              if(mu[T/d]==1)            {
                  f[T]=1ll*f[T]*fib[d]%mod;            }          else if(mu[T/d]==-1)            {
                  f[T]=1ll*f[T]*ifib[d]%mod;            }        }    }  for(int i=1; i<=maxn; ++i)    {
          f[i]=1ll*f[i]*f[i-1]%mod;    }  return 0;}int T,n,m;int main(){
      getprime();  T=read();  while(T--)    {
          n=read();      m=read();      int res=1;      for(int l=1,r; l<=std::min(n,m); l=r+1)        {
              r=std::min(n/(n/l),m/(m/l));          res=1ll*res*quickpow(1ll*f[r]*quickpow(f[l-1],mod-2)%mod,1ll*(n/l)*(m/l)%pmod)%mod;        }      printf("%d\n",res);    }  return 0;}