「2017 山东二轮集训 Day1」第三题

题目描述

火车沉迷垃圾手游不能自拔，他不光自己在玩碧蓝航线，还决定把你拉入坑。

你已经忍无可忍了！你决定出个难题把他按在地上摩擦！正巧你研究了斐波那契数列，也就是 $ f(0) = 0, f(1) = 1 $，否则 $ f(i) = f(i - 1) + f(i - 2) $ 的那个数列，于是你问小火车「我给你 $ n $ 个数 $ k_i $，你知道 $ f(k_i) $ 的最小公倍数吗？」让你惊讶不已的是，小火车竟然一边肝着手游一边报出了巨大的数字！你怀疑他是瞎猜的，所以想知道他回答的到底对不对，不过这个时候你就只需要知道答案对 $ 1000000007 $ 取模的结果啦！

输入格式

第一行一个整数 $ n $。
第二行 $ n $ 个整数表示 $ k_i $。

输出格式

一行一个整数表示答案。

数据范围与提示

对于 $ 20\% $ 的数据，$ k_i \leq 50 $；
对于 $ 50\% $ 的数据，$ k_i \leq 5000 $；
对于 $ 100\% $ 的数据，$ n \leq 50000, k_i \leq 1000000 $。

---

不看题解完全做不来型……

据说是出过很多次的原题……

---

首先有一个预备知识：

最大最小值容斥：

对于整数集合$S$，有下面的关系成立：

$$max\{S\}=\sum_{T\subset S,T\ne \emptyset}(-1)^{|T|+1}min\{T\}$$

不太严谨的证明：

为了方便，下面均省去$T\ne \emptyset$这一限制。

首先我们把所有的数同时加上一个数$d$，使得数列中所有元素都大于$0$。这样做元素间的大小关系不会变，最后只需要减去$d$就能得到最终答案。

（其实就是一个偏移的操作）

那么上式可以改写为:

$$max\{S\}=\sum_{T\subset S}\sum_{i=1}^{min\{T\}}(-1)^{|T|+1}$$

考虑更改枚举顺序，得到：

$$\sum_{T\subset S}\sum_{i=1}^{min\{T\}}(-1)^{|T|+1}=\sum_{i=1}^{\infty}\sum_{k=1}^{cnt[i]}C_{cnt[i]}^{k}(-1)^{k+1}$$

其中$cnt[i]$表示集合$S$中不小于$i$的元素个数。为了凑出二项式定理的形式，把后面变一下形:

$$\sum_{T\subset S}\sum_{i=1}^{min\{T\}}(-1)^{|T|+1}= \sum_{i=1}^{\infty} ((-1) \sum_{k=0}^{cnt[i]} C_{cnt[i]}^k(-1)^k+1)=\sum_{i=1}^{\infty}((-1)[cnt[i]=0]+1)$$

那么当$cnt[i]\ge 0$时后面的贡献都是$1$，当$cnt[i]=0$时后面的贡献是$0$，而$cnt[i]=0$当且仅当$i>max\{S\}$，所以等式成立。

---

下面进入正题：

首先由于$f(n)=f(n-1)+f(n-2)$，有$gcd(f(n),f(n-1))=1$。证明是辗转相除：

$$gcd(f(n),f(n-1))=gcd(f(n)-f(n-1),f(n-1))=gcd(f(n-2),f(n-1))=...=gcd(f(1),f(2))=1$$

然后有一个结论：$f(n+m)=f(n-1)f(m)+f(n)f(m+1)$，证明的话考虑矩阵乘法：

$$\left[ \begin{matrix} f(n)&f(n-1)\\ f(n-1)&f(n-2) \end{matrix} \right] \times \left[ \begin{matrix} 1&1\\ 1&0 \end{matrix} \right]^m= \left[ \begin{matrix} f(n+m)&f(n+m-1)\\ f(n+m-1)&f(n+m-2) \end{matrix} \right]$$

注意到转移矩阵实际上是

$$\left[ \begin{matrix} f(2)&f(1)\\ f(1)&f(0) \end{matrix} \right]$$

所以上式等于

$$\left[ \begin{matrix} f(n)&f(n-1)\\ f(n-1)&f(n-2) \end{matrix} \right] \times \left[ \begin{matrix} f(m+1)&f(m)\\ f(m)&f(m-1) \end{matrix} \right]= \left[ \begin{matrix} f(n+m)&f(n+m-1)\\ f(n+m-1)&f(n+m-2) \end{matrix} \right]$$

那么就证明了$f(n+m)=f(n-1)f(m)+f(n)f(m+1)$。

然后得到结论：

$$gcd(f(a),f(b))=f(gcd(a,b))$$

不妨设$a>b$，把$b$换成上面的$m$,设$a=n+m$,那么化简左边：

$$gcd(f(n+m),f(m))=gcd(f(n-1)f(m)+f(n)f(m+1),f(m))=gcd(f(n)f(m+1),f(m))$$

由于$gcd(f(m),f(m+1))=1$，所以有

$$gcd(f(n+m),f(m))=gcd(f(n),f(m))$$

发现这和辗转相除是一样的形式，所以得到$gcd(f(a),f(b))=f(gcd(a,b))$。

由于$gcd$实际上是把多个数标准分解之后求指数的$min$，而$lcm$则是取$max$，所以在这里考虑最大最小值容斥。

$$lcm\{f_s\}=\prod_i p_i^{max\{k_s\}}= \prod_i p_i^ { \sum _{T\subset S,T\ne \emptyset} (-1)^{|T|+1}min\{T\} } = \prod_{T \subset S,T\ne \emptyset} \prod_ip_i^{(-1)^{|T|+1}min\{T\}}$$

注意到

$$\prod_ip_i^{min\{T\}}=gcd\{f_T\}$$

所以上式化简为：

$$lcm\{f_s\}=\prod_{T\subset S,T\ne \emptyset}gcd\{f_T\}^{(-1)^{|T|+1}}$$

使用$gcd(f(a),f(b))=f(gcd(a,b))$这个结论，得到

$$lcm\{f_s\}=\prod_{T\subset S,T\ne \emptyset}f_{gcd\{T\}} ^{(-1)^{|T|+1}}$$

下面有个很神的操作：构造$\{g_n \}$,使得$f_n=\prod_{d|n}g_d$。

于是可以对上面的式子进一步化简：

$$lcm\{f_s\}=\prod_{T\subset S,T\ne \emptyset} \Big( \prod_{d|gcd\{T\}}g_d \Big) ^{(-1)^{|T|+1}}$$

接下来又按照变换枚举顺序的套路，得到

$$lcm\{f_s\}=\prod_{d=1}^ng_d ^{\sum _{T\subset S,T\ne \emptyset,d|gcd\{T\}} (-1) ^{|T|+1} }$$

关注$g_d$的指数，设它为$h_d$,即：

$$h_d= \sum_{T\subset S,T\ne \emptyset,d|gcd\{T\}} (-1)^{|T|+1}$$

可以看出这里的$T$中所有的元素都必须是$d$的倍数。记$S$中$d$的倍数有$cnt$个，那么有：

$$h_d= \sum_{i=1}^{cnt} C_{cnt}^i(-1)^{i+1} =\sum_{i=0}^{cnt} C_{cnt}^i(-1)^{i+1}+1 =(-1)\sum_{i=0}^{cnt}C_{cnt}^i(-1)^i =(-1)[cnt=0]+1$$

也就是说，只有当$S$中不存在$d$的倍数的时候，$h_d=0$，否则$h_d=1$。

这样就得到了最终的答案式：

$$lcm\{f_s\} =\prod_{d,\exists a\in s,d|a}^ng_d$$

现在唯一的问题就是计算$g_d​$了。根据定义$f_n=\prod_{d|n}g_d​$，得到：

$$g_n=f_n\prod_{d|n,d\ne n}(g_d)^{-1}$$

---

之前提到过，这是一道出过很多次的原题，那么上面的推论对哪些数列是对的呢？

注意到关键在于$gcd(f(a),f(b))=f(gcd(a,b))$这个结论。回顾我们得到它的过程，这个数列如果是$f(n)=af(n-1)+bf(n-2)$，那么要满足下面的条件：

1.$f(0)=0,f(1)=b,f(2)=a$

2.$gcd(a,b)=1$

上面的结论如果有错概不负责

---

代码：

#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 1000005
#define ll long long
using namespace std;
const int mod=1000000007;

int add(int a,int b){a+=b;a-=a<mod?0:mod;return a;}
int sub(int a,int b){a-=b;a+=a<0?mod:0;return a;}
int mul(int a,int b){return (ll)a*b%mod;}
int ksm(int a,int b){
	int ans=1;a%=mod;
	while(b){
		if(b&1)ans=mul(ans,a);
		b>>=1;a=mul(a,a);
	}
	return ans;
}

int N,f[MAXN],g[MAXN],invg[MAXN],Ans;
bool mark[MAXN],app[MAXN];

int main(){
	int i,j,x,mx=0;
	scanf("%d",&N);
	for(i=1;i<=N;i++){
		scanf("%d",&x);
		mx=max(mx,x);
		mark[x]=true;
	}
	
	for(i=2,f[1]=1,g[1]=1;i<=mx;i++)f[i]=add(f[i-1],f[i-2]),g[i]=f[i];
	for(i=1;i<=mx;i++){
		invg[i]=ksm(g[i],mod-2);
		for(j=i+i;j<=mx;j+=i)g[j]=mul(g[j],invg[i]);
	}
	
	for(i=1;i<=mx;i++)
	for(j=i;j<=mx;j+=i){
		app[i]|=mark[j];
		if(app[i])break;
	}
	
	Ans=1;
	for(i=1;i<=mx;i++)if(app[i])Ans=mul(Ans,g[i]);
	printf("%d\n",Ans);
}