题解-[SDOI2017]数字表格
前置知识：
莫比乌斯反演</>
(T) 组测试数据，(f_i) 表示 ( exttt{Fibonacci}) 数列第 (i) 项（(f_0=0)，(f_1=1)，(f_i=f_{i-1}+f_{i-2})），求
[left(prodlimits_{i=1}^nprodlimits_{j=1}^mf_{gcd(i,j)} ight)mod(10^9+7) ]
数据范围：(Tle 1000)，(1le n,mle 10^6)。
本来是水题，但是这个蒟蒻一下犯了好多常见毛病，所以来写篇题解。
-
忘记用生成 (mu) 的线性筛函数了。
-
忘记幂次取模要膜 (varphi(mod)) 了。
假设 (nle m)：
[egin{split}
g(n,m)=&prodlimits_{i=1}^nprodlimits_{j=1}^mf_{gcd(i,j)}\
=&prodlimits_{d=1}^nf_d^{sumlimits_{i=1}^nsumlimits_{j=1}^m[gcd(i,j)=d]}\
=&prodlimits_{d=1}^nf_d^{sumlimits_{i=1}^{lfloorfrac nd
floor}sumlimits_{j=1}^{lfloorfrac md
floor}[gcd(i,j)=1]}\
=&prodlimits_{d=1}^nf_d^{sumlimits_{i=1}^{lfloorfrac nd
floor}sumlimits_{j=1}^{lfloorfrac md
floor}sumlimits_{k|gcd(i,j)}mu(k)}\
=&prodlimits_{d=1}^nf_d^{sumlimits_{k=1}^{lfloorfrac nd
floor}mu(k)sumlimits_{i=1}^{lfloorfrac nd
floor}[k|i]sumlimits_{j=1}^{lfloorfrac md
floor}[k|j]}\
=&prodlimits_{d=1}^nf_d^{sumlimits_{k=1}^{lfloorfrac nd
floor}mu(k)lfloorfrac{n}{dk}
floorlfloorfrac{m}{dk}
floor}\
end{split}
]
然后现在直接分块套分块 (Theta(N+Tn)) 可以得到 (30) 分。
为了 ( exttt{AC})，只好拿 (T=dk) 带入继续走：
[egin{split}
g(n,m)=&prodlimits_{d=1}^nf_d^{sumlimits_{k=1}^{lfloorfrac nd
floor}mu(k)lfloorfrac{n}{dk}
floorlfloorfrac{m}{dk}
floor}\
=&prodlimits_{d=1}^nf_d^{sumlimits_{k=1}^{lfloorfrac nd
floor}mu(k)lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floor}\
=&prodlimits_{T=1}^nprodlimits_{d|T}f_d^{mu(frac{T}{d})lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floor}\
=&prodlimits_{T=1}^nleft(prodlimits_{d|T}f_d^{mu(frac{T}{d})}
ight)^{lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floor}\
end{split}
]
然后括号外面就 (Theta(sqrt n)) 分块，里面就 (Theta(Nlog N)) 预处理出来。
最后时间复杂度：(Theta(Nlog N+Tsqrt n))。
code
#include <bits/stdc++.h>
using namespace std;
//&Start
#define lng long long
#define lit long double
#define kk(i,n) "
"[i==n]
const int inf=0x3f3f3f3f;
const lng Inf=0x3f3f3f3f3f3f3f3f;
//&Data
const int N=1e6,mod=1e9+7;
int t,n,m;
//&Pow
int Pow(int a,int x){
int res=1;
for(;x;a=1ll*a*a%mod,x>>=1)
if(x&1) res=1ll*res*a%mod;
return res;
}
//&Mobius&Fibonacci
bitset<N+10> np;
int p[N+10],cnt,mu[N+10],tp[N+10],f[N+10],g[N+10],h[N+10];
void Mobius(){
np[1]=true;
mu[1]=f[1]=g[1]=h[1]=1;
for(int i=2;i<=N;i++){
if(!np[i]) p[++cnt]=i,mu[i]=-1;
f[i]=(f[i-1]+f[i-2])%mod;
g[i]=Pow(f[i],mod-2);
h[i]=1;
for(int j=1;j<=cnt&&i*p[j]<=N;j++){
np[i*p[j]]=1;
if(i%p[j]==0){mu[i*p[j]]=0;break;}
mu[i*p[j]]=-mu[i];
}
}
for(int k=1;k<=N;k++){ //nlogn 的暴力筛
if(mu[k]==0) continue;
for(int T=k;T<=N;T+=k)
h[T]=1ll*h[T]*(mu[k]==1?f[T/k]:g[T/k])%mod;
}
h[0]=1;
for(int i=1;i<=N;i++) h[i]=1ll*h[i-1]*h[i]%mod;//前缀积
}
//&Main
int main(){
Mobius();//这东西千万不能忘记打
scanf("%d",&t);
for(int ti=1;ti<=t;ti++){
scanf("%d%d",&n,&m);
if(n>m) n^=m^=n^=m;
int res=1,a,x;
for(int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
a=1ll*h[r]*Pow(h[l-1],mod-2)%mod;
x=1ll*(n/l)*(m/l)%(mod-1);//幂次一定一定一定要模(phi(mod))
res=1ll*res*Pow(a,x)%mod;
}
printf("%d
",res);
}
return 0;
}
祝大家学习愉快！