51nod 1355 - 斐波那契的最小公倍数（Min-Max 容斥+莫比乌斯反演）

首先我们知道斐波那契数列的 lcm 是不太容易计算的，但是它们的 gcd 非常容易计算——\(\gcd(f_x,f_y)=f_{\gcd(x,y)}\)，该性质已在我的这篇博客中给出了详细证明，这里就不再赘述了。

考虑怎样将 LCM 转化为 gcd，注意到有个东西叫 Min-Max 容斥，即对于集合 \(S\)，\(\max(S)=\sum\limits_{\varnothing\ne T\subseteq S}(-1)^{|T|+1}\min(T)\)，该性质同样可以应用于 lcm/gcd，因为 \(\operatorname{lcm}\) 即可看作每个数的每个质因子次数取 \(\max\)，\(\gcd\) 即可看作每个数的每个质因子次数取 \(\min\)，因此我们同样有 \(\operatorname{lcm}(S)=\prod\limits_{\varnothing\ne T\subseteq S}\gcd(T)^{(-1)^{|T|+1}}\)，因此我们有 \(ans=\prod\limits_{\varnothing\ne T\subseteq S}f_{\gcd(T)}^{(-1)^{|T|+1}}\)。

到这里还是不太容易直接求，不过考虑有个东西叫莫比乌斯反演，我们记 \(a_d=\sum\limits_{\gcd(T)=d}(-1)^{|T|+1}\)，再记 \(b_d=\sum\limits_{d\mid\gcd(T)}(-1)^{|T|+1}\)，那么显然 \(ans=\prod\limits_{d}f_d^{a_d}\)，接下来考虑怎样求 \(a_d\)，按照莫比乌斯反演的套路有 \(b_d=\sum\limits_{d|n}a_n\)，即 \(b=a*I\)，反演以下可得 \(a=b*\mu\)，即 \(a_d=\sum\limits_{d\mid n}b_n\mu(\dfrac{n}{d})\)，枚举倍数即可求出 \(a_d\)。那么怎么求 \(b_d\) 呢？记 \(U=\{a_x|d\mid a_x\}\)，那么显然所有 \(U\) 的子集都可以成为求和式中的 \(T\)，即 \(b_d=\sum\limits_{i=1}^{|U|}\dbinom{|U|}{i}(-1)^i\)，根据二项式定理该值就等于 \([|U|>0]\)，随便算一下即可，时间复杂度 \(a_i\log a_i\)。

const int MAXV=1e6;

const int MOD=1000000007;

int qpow(int x,int e){

//	eprintf("%d\n",e);

	if(e<0) e+=MOD-1;int ret=1;

	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;

	return ret;

}

int n,mu[MAXV+5],pr[MAXV/10+5],prcnt=0;

bitset<MAXV+5> vis;

void sieve(int n){

	mu[1]=1;

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

		if(!vis[i]){pr[++prcnt]=i;mu[i]=-1;}

		for(int j=1;j<=prcnt&&pr[j]*i<=n;j++){

			vis[pr[j]*i]=1;

			if(i%pr[j]==0) break;

			mu[i*pr[j]]=-mu[i];

		}

	}

}

int is[MAXV+5],f[MAXV+5],fib[MAXV+5];

int main(){

	sieve(MAXV);scanf("%d",&n);

	for(int i=1,x;i<=n;i++) scanf("%d",&x),is[x]=1;

	for(int i=1;i<=MAXV;i++) for(int j=i;j<=MAXV;j+=i) is[i]|=is[j];

	for(int i=1;i<=MAXV;i++) for(int j=i;j<=MAXV;j+=i) f[i]+=is[j]*mu[j/i];

	fib[1]=fib[2]=1;for(int i=3;i<=MAXV;i++) fib[i]=(fib[i-1]+fib[i-2])%MOD;

	int mul=1;for(int i=1;i<=MAXV;i++) mul=1ll*mul*qpow(fib[i],f[i])%MOD;

	printf("%d\n",mul);

	return 0;

}

巴特西

51nod 1355 - 斐波那契的最小公倍数（Min-Max 容斥+莫比乌斯反演）

最新文章

热门文章