Very obviously, 题目让我们求 \(\prod\limits_{i = 1}^n \prod\limits_{j = 1}^m f_{\gcd(i,j)}\)。
按照套路，我们枚举 \(\gcd\)，转化为求 \(\prod\limits_{i = 1}^{\min(n,m)} {f_i}^{\sum\limits_{x = 1}^n \sum\limits_{y = 1}^m [\gcd(x,y) = i]}\)。
把指数那个式子拉出来单独讨论。
根据套路，有 \[\begin{align*}
& \sum\limits_{x = 1}^n \sum\limits_{y = 1}^m [\gcd(x,y) = i] \\
= & \sum\limits_{i | d} \mu(\dfrac d i) \lfloor \dfrac n d \rfloor \lfloor \dfrac m d \rfloor \\
= & \sum\limits_{id \le \min(n,m)} \mu(d) \lfloor \dfrac n {id} \rfloor \lfloor \dfrac m {id} \rfloor
\end{align*}\]
那么 \[\begin{align*} & \prod\limits_{i = 1}^{\min(n,m)} {f_i}^{\sum\limits_{x = 1}^n \sum\limits_{y = 1}^m [\gcd(x,y) = i]} \\ = & \prod\limits_{i = 1}^{\min(n,m)} {f_i}^{\sum\limits_{id \le \min(n,m)} \mu(d) \lfloor \frac n {id} \rfloor \lfloor \frac m {id} \rfloor} \\ = & \prod\limits_{i = 1}^{\min(n,m)} \prod_{d | i} {f_d}^{\mu(\frac i d) \lfloor \frac n i \rfloor \lfloor \frac m i \rfloor} \\ = & \prod\limits_{i = 1}^{\min(n,m)} \left(\prod_{d | i} {f_d}^{\mu(\frac i d)}\right)^{\lfloor \frac n i \rfloor \lfloor \frac m i \rfloor} \end{align*}\]
显然外层的指数可以数论分块，内层这个东西好像不太可做……
那就暴力预处理前缀积啊，反正枚举倍数 \(O(n \log n)\)！
另外此题超卡常，请全开 int 并预处理前缀积的逆元。
代码： 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
using namespace std;
const int N = 1e6;
const int mod = 1e9 + 7;
int t;
int cnt,prime[N + 5],vis[N + 5],mu[N + 5];
int f[N + 5],g[N + 5],prod[N + 5],inv[N + 5],ans;
int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
{
if(b & 1)
ret = (long long)ret * a % mod;
a = (long long)a * a % mod;
}
return ret;
}
int main()
{
f[1] = g[1] = mu[1] = prod[0] = inv[0] = prod[1] = inv[1] = 1;
for(register int i = 2;i <= N;++i)
{
prod[i] = 1,f[i] = (f[i - 1] + f[i - 2]) % mod,g[i] = fpow(f[i],mod - 2);
if(!vis[i])
prime[++cnt] = i,mu[i] = -1;
for(register int j = 1;j <= cnt && i * prime[j] <= N;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
mu[i * prime[j]] = -mu[i];
}
}
for(register int i = 1;i <= N;++i)
if(mu[i])
for(register int j = 1;i * j <= N;++j)
prod[i * j] = (long long)prod[i * j] * (mu[i] == 1 ? f[j] : g[j]) % mod;
for(register int i = 1;i <= N;++i)
prod[i] = (long long)prod[i] * prod[i - 1] % mod,inv[i] = fpow(prod[i],mod - 2);
scanf("%d",&t);
int n,m;
while(t--)
{
ans = 1;
scanf("%d%d",&n,&m);
if(n > m)
swap(n,m);
for(register int l = 1,r;l <= n;l = r + 1)
{
r = min(n / (n / l),m / (m / l));
ans = (long long)ans * fpow((long long)prod[r] * inv[l - 1] % mod,(long long)(n / l) * (m / l) % (mod - 1)) % mod;
}
printf("%d\n",ans);
}
}