[SDOI2017]数字表格

感觉做多了\(DS\)和树图问题，数论水平已经低到小学生水平了。
现在甚至连数论分块都快忘了，昨天看\(dl\ LCT\)博客的时候看到了这题，所以来复健一下。

考虑就是求这样一个东西
\(\prod_{i = 1}^{n}\prod_{j = 1}^{m}f_{gcd(i,j)}\)
考虑斐波那契数列好像在这个题中没有一些好的性质，那只能从我们的熟悉的\(gcd(i,j)\)入手了
\(\prod_{d = 1}^{n}f_d^{\sum_{i = 1}^n\sum_{j = 1}^m gcd(i,j) == d}\)
发现指数是我们的老朋友。
\({\sum_{i = 1}^n\sum_{j = 1}^m gcd(i,j) == d}\)
\({\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} gcd(i,j) == 1}\)
\({\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \sum_{k|gcd(i,j)}\mu(k)}\)
\({\sum_{k = 1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)}{\lfloor \frac{n}{d*k} \rfloor}{\lfloor \frac{m}{d*k} \rfloor}\)
可以（分块套分块）来做了
但是这样只能拿\(30\)分，而且我没写，觉得挺难写的？
那考虑在指数上我们没办法进行更多操作了，拉回原式子来做。
\(\prod_{d = 1}^{n}f_d^{{\sum_{k = 1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)}{\lfloor \frac{n}{d*k} \rfloor}{\lfloor \frac{m}{d*k} \rfloor}}\)
把\(d * x = T\)代入
考虑枚举\(T\)
那么有\(\prod_{T = 1}^{n}\prod_{d|T}f_d^{\mu(\frac{T}{d}){\lfloor \frac{n}{T} \rfloor}{\lfloor \frac{m}{T} \rfloor}}\)
\(\prod_{T = 1}^{n}F(T){{\lfloor \frac{n}{T} \rfloor}{\lfloor \frac{m}{T} \rfloor}}\)
\(F(T)\)可以\(nlogn\)来做
单次询问可以分块做到根号

[SDOI2017]数字表格

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define N 2000005
#define mod 1000000007

ll f[N],inv[N],u[N],isp[N],pm[N],top,F[N],pre[N];

inline ll pow(ll a,ll b){
	ll ans = 1;
	while(b){
		if(b & 1)ans = (a * ans) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return ans % mod;
}

inline void init(){
	f[1] = 1,f[2] = 1;
	for(int i = 3;i <= N - 1;++i)
	f[i] = (f[i - 1] + f[i - 2]) % mod;
	for(int i = 1;i <= N - 1;++i)
	inv[i] = pow(f[i],mod - 2);
	u[1] = 1;
	for(int i = 2; i <= N - 1;i++){
		if(!isp[i]){
			pm[++top] = i;
			u[i] = -1;
		}
		for(int j = 1; j <= top; j++){
			int p = pm[j];
			if(p * i > N - 1) break;
			if(i % p == 0){
				isp[p * i] = 1;
				break;
			}
			isp[p * i] = 1;
			u[p * i] = u[p] * u[i];
		}
	}
	for(int i = 1;i <= N - 1;++i)
	F[i] = 1;
	for(int i = 1;i <= N - 1;++i){
		for(int j = 1;j * i <= N - 1;++j){
			if(u[j] == 1)
			F[i * j] = (F[i * j] * f[i]) % mod;
			if(u[j] == -1)
			F[i * j] = (F[i * j] * inv[i]) % mod;
		}
	}
	for(int i = 2;i <= N - 1;++i)
	F[i] = 1ll * F[i] * F[i - 1] % mod;
}

ll t;

int main(){
	init();
	F[0] = 1;
	scanf("%lld",&t);
	while(t -- ){
		ll n,m;
		scanf("%lld%lld",&n,&m);
		if(n > m)
		std::swap(n,m);
		ll l = 1,r,inv,ans = 1;
		while(l <= n){
			r = std::min(n / (n / l),m / (m / l));
			inv = 1ll * F[r] * pow(F[l - 1],mod - 2) % mod;
			ans = 1ll * ans * pow(inv,1ll * (n / l) * (m / l) % (mod - 1)) % mod;
			l = r + 1;
		} 
		std::cout<<(ans + mod) % mod<<std::endl;
	}
}