[笔记] Fibonacci 的 LCM

给 $n$ 个数 $a_i$,求 $\operatorname{lcm}(f_{a_1},f_{a_2},\cdots f_{a_n})$。$f_i$ 是 Fibonacci 数列,$f_0=0,f_1=1,f_i=f_{i-2}+f_{i-1} (i>1)$。

$1\le n,\max\{a_i\}\le 10^6$

代码链接


思路

首先有结论,$(f_a,f_b)=f_{(a,b)}$。

然后我们考虑 $min-max$ 容斥的 $\gcd-\operatorname{lcm}$ 形式:
$$
\operatorname{lcm}(S)=\prod_{\emptyset\subset T\subseteq S}\gcd(T)^{(-1)^{|T|+1}}
$$
然后考虑式子:
$$
\operatorname{lcm}({f_S})=\prod_{\emptyset\subset T\subseteq S}f_{\gcd(S)}^{(-1)^{|T|+1}}
$$
考虑集合的 $\gcd$ 并不方便。和别的容斥题一样,我们转化为“至少”有这个 $\gcd$,转化到题目中就是我们莫比乌斯反演,我们构造一个 $g_i$ 使得:
$$
f_n=\prod_{d|n}g_d
$$
那么有:
$$
g_n=\prod_{d|n}f_d^{\mu(\frac nd)}
$$
可以调和级数算。然后就有:
$$
\begin{aligned}
\operatorname{lcm}({f_S})&=\prod_{\emptyset\subset T\subseteq S}\left(\prod_{d|gcd(T)}g_d\right)^{(-1)^{|T|+1}}\
&=\prod_d g_d^{h(S,d)}
\end{aligned}
$$
其中
$$
h(S,d)=\sum_{\emptyset\subset T\subseteq S,d|\gcd(T)}(-1)^{|T|+1}
$$
我们假设 $S$ 中有 $k$ 个是 $d$ 的倍数,那么有

$$ \begin{aligned} h(S,d)&=\sum_{i=1}^k\binom ki(-1)^{i+1}\\ &=-\sum_{i=1}^k\binom{i-k-1}{-k-1}\\ &=-\left(\binom0{-k}-\binom{-k}{-k}\right)\\ &=1-\binom0{-k}\\ &=[k\ne0] \end{aligned} $$

然后就很好算了。

代码

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
// Mivik 2020.12.19
#include <mivik.h>

MI cin;

typedef long long qe;

const int nmax = 50005;
const int kmax = 1000005;
const int mod = 1000000007;
const int pmax = kmax;

template<typename T> inline bool getmin(T& a, const T& b) { return a > b && (a = b, true); }
template<typename T> inline bool getmax(T& a, const T& b) { return a < b && (a = b, true); }

int n, lim, a[nmax], f[kmax], g[kmax], mu[kmax], pr[pmax];
bool com[kmax], has[kmax];
inline int pro(int x) { return x >= mod? x - mod: x; }
inline int per(int x) { return x < 0? x + mod: x; }
inline qe ksm(qe x, int p = mod - 2) {
qe ret = 1;
for (; p; p >>= 1, (x *= x) %= mod) if (p & 1) (ret *= x) %= mod;
return ret;
}
inline void sieve(int n) {
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!com[i]) { pr[++pr[0]] = i; mu[i] = -1; }
for (int j = 1, k; j <= pr[0] && (k = i * pr[j]) <= n; ++j) {
com[k] = 1;
if (i % pr[j]) mu[k] = -mu[i];
else break;
}
}
}
int main() {
cin > n;
for (int i = 1; i <= n; ++i) {
const int x(R); has[x] = 1;
getmax(lim, x);
}
f[1] = g[1] = 1;
for (int i = 2; i <= lim; ++i) {
f[i] = pro(f[i - 2] + f[i - 1]);
g[i] = 1;
}
sieve(lim);
for (int i = 1; i <= lim; ++i) {
const int v(f[i]), iv(ksm(v));
for (int j = 1, k = i; k <= lim; ++j, k += i)
if (mu[j] == 1) g[k] = (qe)g[k] * v % mod;
else if (mu[j] == -1) g[k] = (qe)g[k] * iv % mod;
}
int ans = 1;
for (int i = 1; i <= lim; ++i) {
bool found = false;
for (int j = 1, k = i; k <= lim; ++j, k += i)
if ((found |= has[k])) break;
if (found) ans = (qe)ans * g[i] % mod;
}
cout < ans < endl;
}
作者

Mivik

发布于

2020-12-19

更新于

2021-05-31

许可协议

评论