51nod 1355 斐波那契的最小公倍数

题意

我们知道一个结论：(gcd(f_x,f_y)=f_{gcd(x,y)})。
证明见这里。

于是我们考虑将(lcm)向(gcd)方向化，我们知道(lcm)是给指数取(max)，(gcd)是给指数取(min)，因此考虑(min-max)容斥：
(lcm(S)=prodlimits_{p}p^{max(S)}=prodlimits_p p^{sumlimits_{Tin S,T ot=0}(-1)^{|T|+1}min(T)}=prodlimits_{Tin S,T ot=0}gcd(T)^{(-1)^{|T|+1}}=prodlimits_{Tin S,T ot=0}f_{gcd(T)}^{(-1)^{|T|+1}})

构造(g)满足(f_n=prodlimits_{d|n}g_d)，那么有(g_n=prodlimits_{d|n}f_d^{mu(frac{n}{d})})，因为我们两边取个(log)就变成了莫比乌斯反演了。

(prodlimits_{Tin S,T ot=0}f_{gcd(T)}^{(-1)^{|T|+1}})
(=prodlimits_{Tin S,T ot=0}(prodlimits_{d|gcd(T)}g_d)^{(-1)^{|T|+1}})
(=prodlimits_{d}g_d^{sumlimits_{Tin S,T ot=0,d|gcd(T)}(-1)^{|T|+1}})

考虑(g_d)的指数：(sumlimits_{Tin S,T ot=0,d|gcd(T)}(-1)^{|T|+1})
设(d)能整除(S)中的(cnt)个数，那么这个东西就是：
(sumlimits_{i=1}^{cnt}C_{cnt}^i(-1)^{i+1}=[cnt>0])

于是(ans=prodlimits_{exists iin S,d|i}g_d)

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
int n,ans=1;
int mu[maxn],f[maxn],invf[maxn],g[maxn];
bool vis[maxn];
vector<int>prime;
inline int read()
{
    char c=getchar();int res=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int power(int x,int k)
{
	int res=1;
	while(k)
	{
		if(k&1)res=1ll*res*x%mod;
		x=1ll*x*x%mod;k>>=1;
	}
	return res;
}
inline void prework(int n)
{
	vis[1]=mu[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])prime.push_back(i),mu[i]=-1;
		for(unsigned int j=0;j<prime.size()&&i*prime[j]<=n;j++)
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
			mu[i*prime[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]=power(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]=1ll*g[i*j]*f[i]%mod;
			else if(mu[j]==-1)g[i*j]=1ll*g[i*j]*invf[i]%mod;
}
int main()
{
	prework(1e6);
	memset(vis,0,sizeof(vis));
	n=read();
	for(int i=1;i<=n;i++)vis[read()]=1;
	for(int i=1;i<=1000000;i++)
	{
		bool flag=0;
		for(int j=1;i*j<=1000000;j++)flag|=vis[i*j];
		if(!flag)continue;
		ans=1ll*ans*g[i]%mod;
	}
	printf("%d",ans);
	return 0;
}