[51nod1355] 斐波那契的最小公倍数

Description

给定 \(n\) 个正整数 \(a_1,a_2,...,a_n\)，求 \(\text{lcm}(f_{a_1},f_{a_2},...,f_{a_n})\)。其中 \(f_i\) 是斐波那契数列第 \(i\) 项。 \(n\leq 50000,a_i\leq 10^6\)。

Sol

首先关于集合 \(S\) 的\(\text{lcm}\)可以用类似\(\text{min-max}\)容斥的式子搞一下，变成跟\(\gcd\)有关：

\[\text{lcm}(T)=\prod_{S\subseteq T} \gcd(S)^{\left((-1)^{|S|+1}\right)}
\]

所以原式就可以变成：

\[\text{lcm}(f_{\{T\}})=\prod_{S\subseteq T} (f_{\gcd\{S\}})^{\left((-1)^{|S|+1}\right)}
\]

看见这个\(\gcd\)想到莫比乌斯反演

设：

\[f_n=\prod_{d\mid n} g_d
\]

那么：

\[g_n=\frac{f_n}{\prod\limits_{d\mid n\land d\ne n} g_d}
\]

所以原式化为：

\[\begin{aligned}
\text{lcm}(f_{\{T\}})&=\prod_{S\subseteq T}\left(\prod_{d\mid \gcd(S)} g_d \right) ^{\left((-1)^{|S|+1}\right)}\\
&= \prod_{d} g_d^{\;\;\sum\limits_{S\subseteq T\land d\mid \gcd(S)} (-1)^{|T|+1}}
\end{aligned}
\]

然后看看这个式子等于什么：

\[\sum\limits_{S\subseteq T\land d\mid \gcd(S)} (-1)^{|T|+1}
\]

把所有在 \(T\) 中且是 \(d\) 的倍数的 \(x\) 扔进一个新集合 \(S'\) 中，设\(|S'|=n\)，那么：

\[\begin{aligned}
&\sum\limits_{S\subseteq T\land d\mid \gcd(S)} (-1)^{|T|+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-1 \right)\\
=&\epsilon(n\neq 0)
\end{aligned}
\]

也就是说，只要有一个元素是 \(d\) 的倍数，那么 \(g_d\) 就有贡献。

Code

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

typedef double db;

typedef long long ll;

const int N=1e6+5;

const int mod=1e9+7;

int n,mx,a[N],f[N],g[N];

int ksm(int a,int b=mod-2,int ans=1){

	while(b){

		if(b&1) ans=1ll*ans*a%mod;

		a=1ll*a*a%mod;b>>=1;

	} return ans;

}

void init(int n){

	f[1]=1;

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

		f[i]=(f[i-1]+f[i-2])%mod;

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

		for(int j=i+i,p=ksm(f[i]);j<=n;j+=i)

			f[j]=1ll*f[j]*p%mod;

}

signed main(){

	scanf("%d",&n);

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

		scanf("%d",&a[i]),mx=max(mx,a[i]),g[a[i]]=1;

	init(mx); int ans=1;

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

		for(int j=i;j<=mx;j+=i)

			if(g[j]){

				ans=1ll*ans*f[i]%mod;

				break;

			}

	printf("%d\n",ans); return 0;

}

巴特西

[51nod1355] 斐波那契的最小公倍数

Description

Sol

Code

最新文章

热门文章