没看到正解先YY一下
题意要求
\(\prod_{i=1}^{n}\prod_{j=1}^{m}f((i,j))\),其中\(f\)为fibnacci数列
改一下形式变成
\(\prod_{d=1}^{n}f(d)^{\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=d]}\)
\(\prod_{d=1}^{n}f(d)^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[(i,j)=1]}\)
\(\prod_{d=1}^{n}f(d)^{\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor}\)
然后就不会推了。。
然后听说直接根号算复杂度是\(n^{\frac{3}{4}}\)的。。
于是就可以直接过了。。(需要卡卡常
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
// <fib.cpp> - Mon Apr 10 15:23:26 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <algorithm> #include <cstdio> #include <cmath> #include <tr1/unordered_map> using namespace std; typedef long long lol; template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int N=1000001; const int INF=1e9; const int MOD=1e9+7; inline int qpow(int x,int y){ lol res=1; while(y){ if(y&1)res=1ll*res*x%MOD; x=1ll*x*x%MOD; y>>=1; } return res; } int pt,pr[N],mu[N],f[N]; bool np[N]; int mp[2010][2010]; inline int get(int n,int m){ if(n<=2000&&m<=2000&&mp[n][m])return mp[n][m]; int p;lol ans=0; for(int d=1;d<=n;d=p+1){ int x=n/d,y=m/d;p=min(n/x,m/y); ans+=1ll*(mu[p]-mu[d-1])*x*y; } ans%=(MOD-1); if(n<=2000&&m<=2000)mp[n][m]=ans; return ans; } int main(){ int T=gi(); f[1]=1;for(int i=2;i<N;i++)f[i]=(f[i-1]+f[i-2])%MOD; f[0]=1;for(int i=2;i<N;i++)f[i]=1ll*f[i]*f[i-1]%MOD; mu[1]=1; for(int i=2;i<N;i++){ if(!np[i])pr[++pt]=i,mu[i]=-1; for(int j=1;j<=pt&&i*pr[j]<N;j++){ np[i*pr[j]]=1; if(i%pr[j])mu[i*pr[j]]=-mu[i]; else break; } } for(int i=2;i<N;i++)mu[i]+=mu[i-1]; while(T--){ int n=gi(),m=gi(),p,ans=1; if(n>m)swap(n,m); for(int d=1;d<=n;d=p+1){ p=min(n/(n/d),m/(m/d)); ans=1ll*ans*qpow(1ll*f[p]*qpow(f[d-1],MOD-2)%MOD,get(n/d,m/d))%MOD; } printf("%d\n",ans); } return 0; } |