LOJ6102「2017 山东二轮集训 Day1」第三题 or 51nod1355 斐波那契的最小公倍数 题解

Problem

给出 (n) 个数 (a_1,a_2,dots,a_n) ，求出 (operatorname{lcm}(f(a_1),f(a_2,)dots,f(a_n)) mod 10^9+7) ，其中， (f(i)) 代表斐波那契数列第 (i) 项。

Solution

感觉挺妙的，记录一下。 以下 (S,T) 代表一类数的集合。

我们知道斐波那契数列的一个性质：

(gcdleft(f(i),f(j) ight)=fleft(gcd(i,j) ight))

以及类比 (min-max) 容斥，我们可以有：

(operatorname{lcm}(S) = prod_{Tsubseteq S,T eq varnothing}gcd(f(T))^{(-1)^{|T|+1}})

然后就有一个非常妙的变换：

类比莫比乌斯反演，构造数列 (g_1,g_2,dots,g_n) 满足 (f(n) = prod_{d|n}g(d)) ，移项后可得 (g(n) = f(n)prod_{d|n,d eq n}g(d)^{-1})。

然后：

(egin{align} operatorname{lcm}(S) &= prod_{Tsubseteq S,T eq varnothing}gcdleft(f(T) ight)^{(-1)^{|T|+1}} \ &= prod_{Tsubseteq S,T eq varnothing}f(gcd(T))^{(-1)^{|T|+1}}\&=prod_{Tsubseteq S,T e varnothing}fleft(prod_{d|n}g(d) ight)^{(-1)^{|T|+1}}\ &= prod_{dge1}g(d)^{sum_{Tsubseteq S,T e varnothing,d|gcd(T)}(-1)^{|T|+1}}end{align})

对于 (sum_{Tsubseteq S,T e varnothing,d|gcd(T)}(-1)^{|T|+1}) ，若存在 (d|x) , 则为 (1) ，否则为 (0) 。

于是，

(egin{align} operatorname{lcm}(S) &= prod_{dge1}g(d)^{sum_{Tsubseteq S,T e varnothing,d|gcd(T)}(-1)^{|T|+1}} \&= prod_{exists xin S,d|x,dge1}g(d)end{align})

直接计算即可。

Code

#define in read()

typedef long long ll;

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

ll f[M],g[M];
int n,a[N],A;
bool vis[M];

ll qp(ll x,int t){ll res=1;for(;t;t>>=1,x=x*x%mod)if(t&1)res=res*x%mod;return res;}

void getg(){
	f[1] = 1;for(int i = 2;i <= A;i++) f[i] = (f[i-1] + f[i-2]) % mod;
	for(int i = 1;i <= A;i++) g[i] = f[i];
	for(int i = 1;i <= A;i++){
		ll inv = qp(g[i],mod-2);
		for(int j = i+i;j <= A;j += i) g[j] = g[j] * inv % mod;
	}
}

int main (){
	n = in; for(int i = 1;i <= n;i++) a[i] = in,A = max(a[i],A),vis[a[i]] = 1;
	getg(); ll ans = 1;
	for(int i = 1;i <= A;i++){
		bool app = 0;
		for(int j = i;j <= A;j+=i) if(vis[j]) {app = 1;break;}
		if(app) ans = ans * g[i] % mod;
	}
	printf("%lld
",ans);
	return 0;
}