[LOJ 2000][SDOI 2017]数字表格

题目大意

求$\prod_{i = 1}^{n}\prod_{j = 1}^{m}{Fib(gcd(i,j))}$对$10^9+7$取模的结果


思路

先把gcd提到前面:$Ans = \prod_{k = 1}^{min(n,m)}{f(k)^{\sum_{i = 1}^{[\frac{n}{k}]}\sum_{j = 1}^{[\frac{m}{k}]}[gcd(i,j) = 1]}}$

利用Mobius函数性质可得$Ans = \prod_{k = 1}^{min(n,m)}{f(k)^{\sum_{i = 1}^{[\frac{n}{k}]}\sum_{j = 1}^{[\frac{m}{k}]}\sum_{d | gcd(i,j)}{\mu(d)}}}$

然后$Ans = \prod_{k = 1}^{min(n,m)}{f(k)^{\sum_{d = 1}^{[\frac{min(n,m)}{k}]}[\frac{n}{kd}][\frac{m}{kd}]\mu(d)}}$

把$Q = kd$提出,得$Ans = \prod_{Q = 1}^{min(n,m)}{\prod_{k | Q}{f(k)}^{[\frac{n}{Q}][\frac{m}{Q}]\mu(\frac{Q}{k})}}$

即$Ans = \prod_{Q = 1}^{min(n,m)}({\prod_{k | Q}{f(k)}^{\mu(\frac{Q}{k})}})^{[\frac{n}{Q}][\frac{m}{Q}]}$

设$g(Q) = \prod_{k | Q}{f(k)^{\mu(\frac{Q}{k})}}$

最终得到$Ans = \prod_{Q = 1}^{min(n,m)}g(Q)^{[\frac{n}{Q}][\frac{m}{Q}]}$

维护$g(Q)$前缀积分块求(由于取模要求逆元)


Code

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
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
#define N 1000100
#define MOD 1000000007
typedef long long LL;
LL mu[N],f[N],g[N],f1[N],g1[N];
int cnt,prime[N],vis[N];
inline int getint()
{
register int num = 0,sgn = 1;register char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = 0;
for(;isdigit(ch);ch = getchar()) num = (num << 3) + (num << 1) + ch - '0';return sgn ? num : -num;
}
inline int qpow(int a,int b)
{
a %= MOD;int ans = 1;int _a = a,_b = b;
while(b)
{
if(b & 1) ans = 1LL * ans * a % MOD;
a = 1LL * a * a % MOD;
b >>= 1;
}
return ans;
}
inline void calc_fib()
{
f[1] = 1;f[2] = 1;
for(register int i = 3;i < N;i++) f[i] = (0LL + f[i - 1] + f[i - 2]) % MOD;
for(register int i = 1;i < N;i++) f1[i] = qpow(f[i],MOD - 2);
}
inline void init()
{
mu[1] = 1;
for(int i = 2;i < N;i++)
{
if(!vis[i]){prime[++cnt] = i;mu[i] = -1;}
for(int j = 1,k = prime[j];j <= cnt && i * (k = prime[j]) < N;j++)
{
vis[i * k] = 1;
if(i % k) mu[i * k] = -mu[i];
else break;
}
}
calc_fib();
for(int i = 1;i < N;i++) g[i] = 1;
for(int i = 1;i < N;i++) for(int j = 1;i * j < N;j++) if(mu[j]) g[i * j] = 1LL * g[i * j] * ((mu[j] == 1) ? f[i] : f1[i]) % MOD;
for(int i = 2;i < N;i++) g[i] = g[i - 1] * g[i] % MOD;
for(int i = 1;i < N;i++) g1[i] = qpow(g[i],MOD - 2);
}
int solve(int n,int m)
{
int mn = std::min(n,m);int ans = 1;
int last;for(int i = 2;i <= mn;i = last + 1)
{
last = std::min(n / (n / i),m / (m / i));
ans = 1LL * ans * qpow(1LL * g[last] * g1[i - 1] % MOD,1LL * (n / i) * (m / i) % (MOD - 1)) % MOD;
}
return ans;
}
int main()
{
init();
for(int T = getint(),n,m;T;T--)
{
n = getint();m = getint();
printf("%d\n",solve(n,m));
}
return 0;
}