首页 > 代码库 > BZOJ 4816
BZOJ 4816
思路:
$\Pi_{i=1}^n\Pi_{j=1}^m f[gcd(i,j)]$
$=\Pi_{d=1}^n\Pi_{i=1}^{\lfloor\frac{n}{d}\rfloor}\Pi_{j=1}^{\lfloor\frac{m}{d}\rfloor}f[d]*(gcd(i,j)==1)$
$\Sigma_{k=1}^n\Pi_{d|k}\Pi_{i=1}^{\lfloor\frac{n}{dk}\rfloor}\Pi_{j=1}^{\lfloor\frac{m}{dk}\rfloor}*f[d]*\mu(k)$
设dk=t
$=\Sigma_{t=1}^n\Pi_{i=1}^{\lfloor\frac{n}{t}\rfloor}\Pi_{j=1}^{\lfloor\frac{m}{t}\rfloor}\Pi_{d|t}f[d]*\mu(\frac{t}{d})$
$=\Sigma_{t=1}^n\Pi_{d|t}f[d]^{\mu(\frac{t}{d})*\lfloor\frac{n}{t}\rfloor*\lfloor\frac{m}{t}\rfloor}$
设$g(t)=\Pi_{d|t}f[d]^{\mu(\frac{t}{d})}$
$g(t)可以O(nlogn)预处理$
搞个前缀积
剩下的 喜闻乐见 分块
//By SiriusRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=1000005,mod=1000000007;int n,m,cases,f[N],vis[N],prime[N],g[N],mu[N],tot;typedef long long ll;int pow(ll x,int y){ ll res=1; while(y){ if(y&1)res=res*x%mod; x=x*x%mod,y>>=1; }return res;}void shai(){ mu[1]=f[1]=g[0]=1; for(int i=2;i<N;i++){ if(!vis[i])mu[i]=-1,prime[++tot]=i; for(int j=1;i*prime[j]<N&&j<=tot;j++){ vis[i*prime[j]]=1,mu[i*prime[j]]=-mu[i]; if(i%prime[j]==0){mu[i*prime[j]]=0;break;} } f[i]=(f[i-1]+f[i-2])%mod; } for(int i=1;i<N;i++)g[i]=1; for(int i=1;i<N;i++){ int ni=pow(f[i],mod-2); for(int j=1;i*j<N;j++){ if(mu[j]==1)g[i*j]=(1ll*g[i*j]*f[i])%mod; else if(mu[j]==-1)g[i*j]=(1ll*g[i*j]*ni)%mod; } } for(int i=1;i<N;i++)g[i]=(1ll*g[i]*g[i-1])%mod;}int main(){ shai(); scanf("%d",&cases); while(cases--){ scanf("%d%d",&n,&m); if(n>m)swap(n,m); ll ans=1; for(int l=1,r;l<=n;l=r+1){ r=min(n/(n/l),m/(m/l)); ans=ans*pow(1ll*g[r]*pow(g[l-1],mod-2)%mod,1ll*(n/l)*(m/l)%(mod-1))%mod; }printf("%lld\n",ans); }}
BZOJ 4816
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。