\(\mathcal{Description}\)

Link.

令 \(f\) 为 \(\text{Fibonacci}\) 数列，给定 \(\{a_n\}\)，求：

\[\operatorname{lcm}\{f_{a_1},f_{a_2},\cdots,f_{a_n}\}\bmod(10^9+7)
\]

\(n\le5\times10^4\)，\(a_i\le10^6\)。

\(\mathcal{Solution}\)

你得知道：

\[\gcd(f_i,f_j)=f_{\gcd(i,j)}\tag1
\]

\[\operatorname{lcm}(S)=\prod_{T\subseteq S\land T\not=\varnothing}\gcd(T)^{(-1)^{|T|+1}}\tag2
\]

\((1)\) 老经典的结论了；\((2)\) 本质上是一个 \(\text{Min-Max}\) 反演。

记 \(F=\{f_{a_n}\},S=\{a_n\},m=\max(S)\)，开始推导：

\[\begin{aligned}
\operatorname{lcm}(F)&=\prod_{T\subseteq F\land T\not=\varnothing}\gcd(T)^{(-1)^{|T|+1}}\\
&=\prod_{T\subseteq S\land T\not=\varnothing}f_{\gcd(T)}^{(-1)^{|T|+1}}\\
&=\prod_{d=1}^mf_d^{\sum_{T\subseteq S\land T\not=\varnothing\land\gcd(T)=d}(-1)^{|T|+1}}
\end{aligned}
\]

记 \(f_d\) 的指数为 \(g(d)\)，令 \(h(d)=\sum_{T\subseteq S\land T\not=\varnothing\land d|\gcd(T)}(-1)^{|T|+1}=1-\sum_{T\subseteq S\land d|\gcd(T)}(-1)^{|T|}\)。设有 \(c_d\) 个 \(a_x\) 是 \(d\) 的倍数，那么：

\[\sum_{T\subseteq S\land d|\gcd(T)}(-1)^{|T|}=\sum_{s=0}^{c_d}\binom{c_d}s(-1)^s
\]

二项式展开逆用，后式为 \((1-1)^{c_d}=[c_d=0]\)，所以 \(h(d)=[c_d\not=0]\)。最后利用 \(h\) 反演出 \(g\)：

\[g(d)=\sum_{d|n}h(n)\mu(\frac{n}d)
\]

\(\mathcal O(n\ln n)\) 把 \(g\) 求出来就好。

\(\mathcal{Code}\)

/* Clearink */

#include <cstdio>

inline int rint () {

	int x = 0; int f = 1; char s = getchar ();

	for ( ; s < '0' || '9' < s; s = getchar () ) f = s == '-' ? -f : f;

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x * f;

}

inline void wint ( int x ) {

	if ( 9 < x ) wint ( x / 10 );

	putchar ( x % 10 ^ '0' );

}

const int MAXN = 5e4, MAXA = 1e6, MOD = 1e9 + 7;

int pn, pr[MAXA + 5], mu[MAXA + 5];

int n, a[MAXN + 5], fib[MAXA + 5], indx[MAXA + 5];

bool buc[MAXA + 5], vis[MAXA + 5];

inline int qkpow ( int a, int b, const int p = MOD ) {

	int ret = 1; b = ( b % ( p - 1 ) + ( p - 1 ) ) % ( p - 1 );

	for ( ; b; a = 1ll * a * a % p, b >>= 1 ) ret = 1ll * ret * ( b & 1 ? a : 1 ) % p;

	return ret;

}

inline void init ( const int n ) {

	mu[1] = 1;

	for ( int i = 2; i <= n; ++ i ) {

		if ( !vis[i] ) mu[pr[++ pn] = i] = -1;

		for ( int j = 1, t; j <= pn && ( t = i * pr[j] ) <= n; ++ j ) {

			vis[t] = true;

			if ( !( i % pr[j] ) ) break;

			mu[t] = -mu[i];

		}

	}

	fib[1] = 1;

	for ( int i = 1; i <= n; ++ i ) {

		if ( i > 1 ) fib[i] = ( fib[i - 1] + fib[i - 2] ) % MOD;

		for ( int j = i; j <= n; j += i ) {

			buc[i] |= buc[j];

		}

	}

	for ( int i = 1; i <= n; ++ i ) {

		for ( int j = 1, t = n / i; j <= t; ++ j ) {

			indx[i] += mu[j] * buc[i * j];

		}

	}

}

int main () {

	n = rint ();

	int mxa = 0;

	for ( int i = 1; i <= n; ++ i ) {

		buc[a[i] = rint ()] = true;

		if ( mxa < a[i] ) mxa = a[i];

	}

	init ( mxa );

	int ans = 1;

	for ( int i = 1; i <= mxa; ++ i ) {

		ans = 1ll * ans * qkpow ( fib[i], indx[i] ) % MOD;

	}

	wint ( ans ), putchar ( '\n' );

	return 0;

}

\(\mathcal{Details}\)

对 \(\text{Min-Max}\) 要敏感一点呐……

巴特西

Solution -「51nod 1355」斐波那契的最小公倍数

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

\(\mathcal{Details}\)

最新文章

热门文章