(mathcal{Description})
Link.
令 (f) 为 ( ext{Fibonacci}) 数列，给定 ({a_n})，求：
[operatorname{lcm}{f_{a_1},f_{a_2},cdots,f_{a_n}}mod(10^9+7)
]
(nle5 imes10^4)，(a_ile10^6)。
(mathcal{Solution})
你得知道：
[gcd(f_i,f_j)=f_{gcd(i,j)} ag1
]
[operatorname{lcm}(S)=prod_{Tsubseteq Sland T
ot=varnothing}gcd(T)^{(-1)^{|T|+1}} ag2
]
((1)) 老经典的结论了；((2)) 本质上是一个 ( ext{Min-Max}) 反演。
记 (F={f_{a_n}},S={a_n},m=max(S))，开始推导：
[egin{aligned}
operatorname{lcm}(F)&=prod_{Tsubseteq Fland T
ot=varnothing}gcd(T)^{(-1)^{|T|+1}}\
&=prod_{Tsubseteq Sland T
ot=varnothing}f_{gcd(T)}^{(-1)^{|T|+1}}\
&=prod_{d=1}^mf_d^{sum_{Tsubseteq Sland T
ot=varnothinglandgcd(T)=d}(-1)^{|T|+1}}
end{aligned}
]
记 (f_d) 的指数为 (g(d))，令 (h(d)=sum_{Tsubseteq Sland T ot=varnothingland d|gcd(T)}(-1)^{|T|+1}=1-sum_{Tsubseteq Sland d|gcd(T)}(-1)^{|T|})。设有 (c_d) 个 (a_x) 是 (d) 的倍数，那么：
[sum_{Tsubseteq Sland d|gcd(T)}(-1)^{|T|}=sum_{s=0}^{c_d}inom{c_d}s(-1)^s
]
二项式展开逆用，后式为 ((1-1)^{c_d}=[c_d=0])，所以 (h(d)=[c_d ot=0])。最后利用 (h) 反演出 (g)：
[g(d)=sum_{d|n}h(n)mu(frac{n}d)
]
(mathcal O(nln 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 ( '
' );
return 0;
}
(mathcal{Details})
对 ( ext{Min-Max}) 要敏感一点呐……