题目大意
求 \[\prod \limits_{i = 1}^{n} \prod \limits_{i = 1}^{m} f_{\gcd(i, j)}\] 其中 \(f_i\) 为斐波那契数列。
题解
一看就先把 \(\gcd\) 提出来，老套路题了。
不妨设 \(n \le m\)，则
\[\begin{aligned}
原式 &= \prod \limits_{d = 1}^{n} \prod \limits_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \prod \limits_{i = 1}^{\lfloor \frac{m}{d} \rfloor} f_d^{[\gcd(i, j) = 1]}\\
&= \prod \limits_{d = 1}^n f_d^{\sum \limits_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum \limits_{i = 1}^{\lfloor \frac{m}{d} \rfloor}[\gcd(i, j) = 1]}\\
&= \prod \limits_{d = 1}^n f_d^{\sum\limits_{g = 1}^n \mu(g)\lfloor\frac{n}{dg}\rfloor\lfloor\frac{m}{dg}\rfloor}\\
&= \prod \limits_{k = 1}^n(\prod \limits_{d = 1}^nf_d^{\mu({\frac{k}{d}})})^{\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor}
\end{aligned}\]
然后右上角那两个 \(\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor\) 可以整除分块，剩下的问题是如何处理出 \(\prod \limits_{d = 1}^nf_d^{\mu({\frac{k}{d}})}\)。
令 \(F(k) = \prod \limits_{d = 1}^nf_d^{\mu({\frac{k}{d}})}\)
因为需要数论分块，考虑前缀积。
这一块有参考 rqy 的 blog。
和线性递推逆元类似的方法，我们可以得到 \(F(k)\) 的前缀积以及其逆元。我参考了 qwaszx 的博客。
然后要注意的细节是快速幂里面是 \((n / l) * (m / l) \bmod{p - 1}\)。
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
71
| #include <algorithm>
#include <cstdio>
const int N = 1e6 + 10;
const int MOD = 1e9 + 7;
bool vis[N];
int pri[N], cnt;
void Sieve() {
for (int i = 2; i < N; ++i) {
if (!vis[i])
pri[++cnt] = i;
for (int j = 1; j <= cnt && i * pri[j] < N; ++j) {
vis[i * pri[j]] = true;
if (i % pri[j] == 0)
break;
}
}
}
int FastPow(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = 1ll * a * a % MOD)
if (b & 1)
res = 1ll * res * a % MOD;
return res;
}
int f[N], g[N];
int mf[N], invf[N];
void Init() {
int n = N - 1;
f[1] = mf[1] = invf[0] = invf[1] = 1;
for (int i = 2; i <= n; ++i)
f[i] = (f[i - 1] + f[i - 2]) % MOD, mf[i] = 1ll * mf[i - 1] * f[i] % MOD;
int t = FastPow(mf[n], MOD - 2);
for (int i = n; i >= 2; --i)
invf[i] = 1ll * t * mf[i - 1] % MOD, t = 1ll * t * f[i] % MOD;
for (int i = 1; i <= cnt; ++i)
for (int j = n / pri[i]; j >= 1; --j) {
f[j * pri[i]] = 1ll * f[j * pri[i]] * invf[j] % MOD;
invf[j * pri[i]] = 1ll * invf[j * pri[i]] * f[j] % MOD;
}
for (int i = 2; i <= n; ++i)
f[i] = 1ll * f[i] * f[i - 1] % MOD,
invf[i] = 1ll * invf[i] * invf[i - 1] % MOD;
}
int main() {
int T;
scanf("%d", &T);
Sieve();
Init();
while (T--) {
int n, m, res = 1;
scanf("%d%d", &n, &m);
if (n > m)
std::swap(n, m);
for (int l = 1, r = 0; l <= std::min(n, m); l = r + 1) {
r = std::min(n / (n / l), m / (m / l));
res = (1ll * res *
FastPow(1ll * f[r] * invf[l - 1] % MOD, 1ll * (n / l) * (m / l) % (MOD - 1))) %
MOD;
}
printf("%d\n", res);
}
return 0;
}
|
就这代码跑了 Luogu 第 7？？？要是我再卡卡常。。。
\(O(n \log \log n)\) 好啊！