[笔记] 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} $$

然后就很好算了。

代码

// 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;
}