51Nod1355 斐波那契的最小公倍数

斐波那契的最小公倍数

定义斐波那契数列 (f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}~(ngeq 2))。

给出 (n) 个整数 (a_1,a_2,dots,a_n)，求 ( ext{lcm}{f_{a_1},f_{a_2},dots,f_{a_n}})。

(n leq 5 imes 10^4,a_i leq 10^6)。

题解

https://blog.csdn.net/alan_cty/article/details/73928751
https://blog.csdn.net/werkeytom_ftd/article/details/73730392

最大公约数

斐波那契数列的最大公约数定理：

[gcd{f_n,f_m}=f_{gcd{n,m}} ]

证明可分为四部分。

第一部分

[gcd{f_n,f_{n-1}}=1 ]

使用归纳法证明。

(n=1)时，(gcd{f_1,f_0}=1) 显然成立。
(n geq 2) 时，

[gcd{f_n,f_{n-1}}=gcd{f_{n-1}+f_{n-2},f_{n-1}}\ =gcd{f_{n-2},f_{n-1}}=1 ]

第二部分

[f_{n+m}=f_{n-1}f_m+f_{n}f_{m+1} ]

使用归纳法证明。

(m=0) 时，(f_{n+0}=f_{n-1}f_0+f_nf_1 ightarrow f_n=f_n) 显然成立；
(m=1) 时，(f_{n+1}=f_{n-1}f_1+f_nf_2 ightarrow f_{n+1}=f_{n-1}+f_n) 显然成立；
(m geq 2) 时，

[f_{n+m}=f_{n+m-1}+f_{n+m-2}\ =f_{n-1}f_{m-1}+f_nf_m+f_{n-1}f_{m-2}+f_nf_{m-1}\ =f_{n-1}(f_{m-1}+f_{m-2})+f_n(f_m+f_{m-1})\ =f_{n-1}f_m+f_nf_{m+1} ]

第三部分

[gcd{f_{n+m},f_n}=gcd{f_n,f_m} ]

证明如下，

[gcd{f_{n+m},f_n}=gcd{f_{n-1}f_m+f_nf_{m+1},f_n}\ =gcd{f_{n-1}f_m,f_n}\ =gcd{f_m,f_n} ]

第四部分

[gcd{f_n,f_m}=f_{gcd{n,m}} ]

第三部分的结论也可写作 (gcd{f_n,f_m}=gcd{f_{n-m},f_m})。然后就是辗转相减法的过程。

容斥与反演

构造数列 (g)，满足

[f_n=prod_{d|n}g_d ]

注意这里是乘法而不是加法。可以用莫比乌斯反演求出 (g)，

[g_n=prod_{d|n}f_d^{mu(n/d)} ]

我倒是第一次见连乘的莫比乌斯反演。证明考虑取个对数。

因为 (gcd) 更棒，所以我们通过容斥把 ( ext{lcm}) 转化成 (gcd)。

[ ext{lcm}_{iin S}{f_i}=prod_{Tsubseteq S}gcd_{iin T}{f_i}^{-1^{|T|+1}} ]

这个容斥本质上是质因子指数的min-max容斥。

[ ext{lcm}_{iin S}{f_i}=prod_{Tsubseteq S}f_{gcd_{iin T}{i}}^{-1^{|T|+1}}\ =prod_{Tsubseteq S}left(prod_{d|gcd_{iin T}{i}}g_d ight)^{-1^{|T|+1}}\ =prod_{d}g_d^{sum_{Tsubseteq S,d|gcd_{iin T}{i}}(-1)^{|T|+1}} ]

观察 (g_d) 的指数

[sum_{Tsubseteq S,d|gcd_{iin T}{i}}(-1)^{|T|+1} ]

设 (d) 整除 (S) 中 (t) 个数。若 (t=0) 显然指数为 (0)，否则为

[sum_{i=1}^tinom{t}{i}(-1)^{i+1}=-sum_{i=1}^tinom{t}{i}1^{t-i}(-1)^i\ =-((1-1)^t-1)=1 ]

因此我们得到

[ ext{lcm}_{iin S}{f_i}=prod_{exists iin S,d|i} g_d ]

时间复杂度 (O(vlog v))。

CO int N=1e6+10;
int pri[N],tot,mu[N];
int f[N],invf[N],g[N];
bool vis[N];

int main(){
	pri[1]=1,mu[1]=1;
	for(int i=2;i<N;++i){
		if(!pri[i]) pri[++tot]=i,mu[i]=-1;
		for(int j=1;j<=tot and i*pri[j]<N;++j){
			pri[i*pri[j]]=1;
			if(i%pri[j]==0){
				mu[i*pri[j]]=0;
				break;
			}
			mu[i*pri[j]]=-mu[i];
		}
	}
	f[0]=0,f[1]=1;
	for(int i=2;i<N;++i) f[i]=add(f[i-1],f[i-2]);
	for(int i=1;i<N;++i) invf[i]=fpow(f[i],mod-2);
	for(int i=1;i<N;++i) g[i]=1;
	for(int i=1;i<N;++i)for(int j=1;i*j<N;++j){
		if(mu[j]==1) g[i*j]=mul(g[i*j],f[i]);
		else if(mu[j]==-1) g[i*j]=mul(g[i*j],invf[i]);
	}
	for(int n=read<int>();n--;) vis[read<int>()]=1;
	int ans=1;
	for(int i=1;i<N;++i){
		bool flag=0;
		for(int j=1;i*j<N;++j)if(vis[i*j]){
			flag=1;break;
		}
		if(flag) ans=mul(ans,g[i]);
	}
	printf("%d
",ans);
	return 0;
}