【51nod 1355】 斐波那契的最小公倍数

2018-12-25 10:03:45

### 题目描述

$$\text{lcm}(f_{a_1},f_{a_2},f_{a_3},f_{a_4},\cdots,f_{a_n}) \bmod {1000000007}$$

$2 \le n \le 50000$

$1 \le a_i \le 10^6$

### 题解

$$\text{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$$

$$\text{lcm}(a,b,c)=\frac{abc\gcd(a,b,c)}{\gcd(a,b)\gcd(b,c)\gcd(a,c)}$$

$$\text{lcm}(S)=\prod_{\emptyset \ne T \subseteq S} \gcd(T)^{\left( (-1)^{\mid T \mid + 1} \right)}$$

$$\gcd(f_i,f_j)=f_{\gcd(i,j)}$$

\begin{aligned} &\text{lcm}(f_{a_1},f_{a_2},f_{a_3},f_{a_4},\cdots,f_{a_n}) \\ =&\prod_{\emptyset \ne T \subseteq S} \gcd({f_{T}})^{\left( (-1)^{\mid T \mid + 1} \right)} \\ =&\prod_{\emptyset \ne T \subseteq S} f_{\gcd(T)}^{\left( (-1)^{\mid T \mid + 1} \right)} \\ \end{aligned}

$$f=g \times 1 \Leftrightarrow g=f \times \mu$$

$$f_n=\prod_{d \mid n} g_d \Leftrightarrow g_n=\prod_{d \mid n}f_d^{\mu(\frac{n}{d})}$$

$$f_n=\prod_{d \mid n} g_d \Rightarrow g_n=\frac{f_n}{\prod_{d \mid n \wedge d \ne n}g_d}$$

\begin{aligned} &\prod_{\emptyset \ne T \subseteq S} f_{\gcd(T)}^{\left( (-1)^{\mid T \mid + 1} \right)} \\ =&\prod_{\emptyset \ne T \subseteq S} \left(\prod_{d \mid \gcd(T)}g_d\right)^{\left( (-1)^{\mid T \mid + 1} \right)} \\ =&\prod_{d} g_d^{\sum_{\emptyset \ne T \subseteq S \wedge d \mid \gcd(T)}(-1)^{\mid T \mid + 1}} \end{aligned}

$$\sum_{\emptyset \ne T \subseteq S \wedge d \mid \gcd(T)} (-1)^{\mid T \mid +1}$$

\begin{aligned} &\sum_{\emptyset \ne T \subseteq S \wedge d \mid \gcd(T)} (-1)^{\mid T \mid +1} \\ =&\sum_{i=1}^{n} {n \choose i} (-1)^{i+1} \\ =&(-1) \left(\sum_{i=1}^{n}{n \choose i}(-1)^{i}\right) \\ =&(-1) \left((1-1)^n-{n \choose 0} (-1)^{0}\right) \\ =&[n \ne 0] \end{aligned}

### 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 10, mod = 1e9 + 7;

int n, mx, a[N]; ll fib[N], g[N], cnt[N], ans = 1;

ll pw(ll a, ll b) {
ll r = 1;
for( ; b ; b >>= 1, a = a * a % mod)
if(b & 1)
r = r * a % mod;
return r;
}

int main() {
scanf("%d", &n);
for(int i = 1 ; i <= n ; ++ i) scanf("%d", &a[i]), mx = max(mx, a[i]), cnt[a[i]] ++;
fib[1] = g[1] = 1; for(int i = 2 ; i <= mx ; ++ i) g[i] = fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
for(ll i = 1 ; i <= mx ; ++ i)
for(ll j = 2, inv = pw(g[i], mod - 2) ; i * j <= mx ; ++ j)
g[i * j] = g[i * j] * inv % mod;
for(ll i = 1 ; i <= mx ; ++ i)
for(ll j = 1 ; i * j <= mx ; ++ j)
if(cnt[i * j]) {
ans = ans * g[i] % mod;
break;
}
printf("%lld\n", (ans % mod + mod) % mod);
}
• star
首页