OI - 斐波那契的最小公倍数(51nod) | Lucky_Glass's Blog
0%

OI - 斐波那契的最小公倍数(51nod)

快乐猜结论


# 题面

> Linked 51nod-1355

点击展开/折叠 题面

数列 $f_n$ 表示 $f_0=0,f_1=1$,$f_n=f_{n-1}+f_{n-2}$($n\ge 2$)。

给定 $n$ 以及 $a_1,a_2,\dots,a_n$,($1\le n\le50000,1\le a_i\le10^6$)求:

$$\text{lcm}(f_{a_1},f_{a_2},\dots,f_{a_n})\bmod 10^9+7$$


# 解析

莫名其妙猜了一下 min-max反演,然后式子都没推完就把结论给猜出来了 (。^▽^)

首先有一个一般性的结论,与斐波那契无关。

假如要求 $\text{lcm}(a_1,a_2,\dots,a_n)$,先把每个数质因数分解 $a_k=\prod p_i^{b_{i,k}}$,然后 lcm 就是求

定义全集 $\mathbb U=\{1,2,\dots,n\}$,于是对指数来 min-max 反演:

根据指数的相关运算可以把指数中的 $\Sigma$ 提出来。

这就是对若干数求 lcm 的min-max反演方法。

不严谨地书写,$\gcd(\mathbb S)$ 表示 $\mathbb S$ 中所有数的 gcd;$x\mid\mathbb S$ 表示 $x$ 整除 $\mathbb S$ 中的所有数

那么运用到这道题就是,令全集 $\mathbb V=\{a_1,a_2,\dots,a_n\}$,又运用到斐波那契数列的广为人知的结论,则答案为

既然有 gcd,就可以莫比乌斯反演了 ╰( ̄ω ̄o)

令 $h(t)=\sum\limits_{\mathbb S\in\mathbb V,t\mid\mathbb S}(-1)^{|\mathbb S|-1}$,这相当于什么?若 $t\mid\mathbb S$,则 $\mathbb S$ 中的每个元素都是 $t$ 的倍数;换言之,如果 $t\mid a_k$,$a_k$ 就可以成为 $\mathbb S$ 的元素。

所以预处理出 $c_t$ 表示有多少个 $a_k$ 满足 $t\mid a_k$,则满足 $t\mid\mathbb S$ 的 $\mathbb S$ 一定是这 $c_t$ 个元素的子集。

$h(t)$ 相当于计算“大小为奇数的 $\mathbb S$ 的数量-大小为偶数的 $\mathbb S$ 的数量”。

  • 若在 $c_t$($c_t\ge 1$)个元素构成的集合任意取子集(包括空集),奇数集的个数等于偶数集的个数,但是现在不能取空集,所以偶数集个数减一,$h(t)=1$;
  • 若 $c_t=0$,则 $h(t)=0$。

即 $h(t)=[c_t>0]$。

继续推原来的式子:

这样就可以计算了。具体地说,先 $O(n\sqrt{a_i})$ 处理出 $c_t$,从而可以得到 $h(t)=[c_t>0]$;然后线性筛出 $\mu$;计算答案则直接暴力枚举 $d,t$,是调和级数的复杂度。


# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5e4+10,M=1e6+10,MOD=1e9+7;
#define ci const int &

int n,nprm;
int num[N],mu[M],prm[M/10],cnt[M],fib[M];
bool vis[M];

inline int Add(ci a,ci b,ci mod=MOD){return a+b>=mod? a+b-mod:a+b;}
inline int Sub(ci a,ci b,ci mod=MOD){return a-b<0? a-b+mod:a-b;}
inline int Mul(ci a,ci b,ci mod=MOD){return 1ll*a*b%mod;}
inline int Pow(int a,int b,ci mod=MOD){int r=1;while(b){if(b&1)r=Mul(r,a,mod);a=Mul(a,a,mod),b>>=1;}return r;}
void Init(){
mu[1]=1;
for(int i=2;i<M;i++){
if(!vis[i]) mu[prm[++nprm]=i]=MOD-2;
for(int j=1;j<=nprm && prm[j]*i<M;j++){
vis[prm[j]*i]=true;
if(i%prm[j]==0) break;
mu[i*prm[j]]=Sub(0,mu[i],MOD-1);
}
}
fib[0]=0,fib[1]=1;
for(int i=2;i<M;i++) fib[i]=Add(fib[i-1],fib[i-2]);
}
int main(){
Init();
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&num[i]);
for(int j=1;j*j<=num[i];j++)
if(num[i]%j==0){
cnt[j]++;
if(j*j!=num[i]) cnt[num[i]/j]++;
}
}
int ans=1;
for(int i=1;i<M;i++){
int tot=0;
for(int t=i;t<M;t+=i)
tot=Add(tot,Mul(mu[t/i],cnt[t]>0,MOD-1),MOD-1);
// printf("%d: %d\n",i,tot);
ans=Mul(ans,Pow(fib[i],tot));
}
printf("%d\n",ans);
return 0;
}

THE END

Thanks for reading!