Description：

求 $n$ 个数字的斐波那契函数的最小公倍数。

$1\le n \le 50000,1\le ai\le 1000000$

Solution：

首先有结论 $gcd(f(i),f(j))=f(gcd(i,j))$ ，但是对 $lcm$ 不成立。

还有结论： $\begin{align}lcm\{S\}=\prod_{T\subseteq S,T\ne\emptyset}gcd\{T\}^{(-1)^{|T|+1}}\end{align}$

于是 $\begin{align}lcm\{f(S)\}=\prod_{T\subseteq S,T\ne \empty}gcd\{f(T)\}^{(-1)^{|T|+1}}=\prod_{T\subseteq S,T\ne \empty}f(gcd\{T\})^{(-1)^{|T|+1}}\end{align}$

构造数列 $g_n$ 满足 $\begin{align}f(n)=\sum_{d|n}g(d)\end{align}$

$\begin{align}lcm\{f(S)\}=\prod_{T\subseteq S,T\ne\empty}\prod_{\forall i\in T,d|i}g(d)^{(-1)^{|T|+1}}=\prod g(d)^{\sum_{T\subseteq S,T\ne\empty,\forall i\in T,d|i}(-1)^{|T|+1}}\end{align}$

设右上角的指数为 $k$ 。分类讨论。

如果 $\exists\ w\in S,d|w$ ，那么由容斥原理得最后这个值一定是 $1$ ，因为设 $S$ 中有 $t$ 个数满足 $s|w$ ， $C_t^1-C_t^2+C_t^3-\cdots+(-1)^{t+1}C_t^t=1$ ，因为由二项式定理得 $\begin{align}(1+(-1))^t=\sum_{i=0}^tC_t^i\times(-1)^i=0\end{align}$ ， $\begin{align}原式-C_t^0=\sum_{i=0}^tC_t^i\times(-1)^{i+1}=0\end{align}$ ，故原式 $=1$ 。

所以当 $\exists \ w\in S,d|w$ 时， $k=1$ ，否则 $k=0$ 。

最终答案为 $\begin{align}lcm\{f(S)\}=\prod_{\exists w\in S,d|w}g(d)\end{align}$

至于 $g$ 数组怎么求，可以由 $\begin{align}g(n)=f(n)\times (\prod_{d|n,d \ne n}g(d))^{-1}\end{align}$ 这个式子 $O(n\ln n)$ 求。

最后还有一个问题，就是 $\exists w\in S,d|w$ 这个条件怎么处理，可以标记每个数，对于每个 $d$ 枚举他的所有倍数，还是 $O(n\ln n)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n;

#define MAXN 1000010

ll a[MAXN];

ll f[MAXN],g[MAXN];

bool tag[MAXN]; 

#define MOD 1000000007ll

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int main()

{

	scanf("%lld",&n);

	ll maxa = 0;

	for(ll i = 1;i <= n;++i)scanf("%lld",&a[i]);

	memset(tag,false,sizeof(tag));

	for(ll i = 1;i <= n;++i)tag[a[i]] = true;

	for(ll i = 1;i <= n;++i)maxa = max(maxa,a[i]);

	f[0] = 0;f[1] = 1;

	for(ll i = 2;i <= maxa;++i)f[i] = (f[i - 1] + f[i - 2]) % MOD;

	for(ll i = 1;i <= maxa;++i)g[i] = f[i];

	for(ll i = 1;i <= maxa;++i)

		for(ll j = i + i,inv = power(g[i],MOD - 2);j <= maxa;j += i)

			g[j] = g[j] * inv % MOD;

	ll ans = 1;

	for(int i = 1;i <= maxa;++i)

	{

		bool t = false;

		for(int j = i;j <= maxa;j += i)t |= tag[j];

		if(t)ans = ans * g[i] % MOD;

	}

	cout << ans << endl;

	return 0;

}