51nod 1355 斐波那契的最小公倍数(min-max容斥+莫比乌斯反演)

· · 个人记录

题意

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

于是我们考虑将lcm向\gcd方向化，我们知道lcm是给指数取\max，\gcd是给指数取\min，因此考虑\min-\max容斥：

lcm(S)=\prod\limits_{p}p^{\max(S)}=\prod\limits_p p^{\sum\limits_{T\in S,T\not=0}(-1)^{|T|+1}\min(T)}=\prod\limits_{T\in S,T\not=0}\gcd(T)^{(-1)^{|T|+1}}=\prod\limits_{T\in S,T\not=0}f_{\gcd(T)}^{(-1)^{|T|+1}}

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

\prod\limits_{T\in S,T\not=0}f_{\gcd(T)}^{(-1)^{|T|+1}} =\prod\limits_{T\in S,T\not=0}(\prod\limits_{d|\gcd(T)}g_d)^{(-1)^{|T|+1}} =\prod\limits_{d}g_d^{\sum\limits_{T\in S,T\not=0,d|\gcd(T)}(-1)^{|T|+1}}

考虑g_d的指数：\sum\limits_{T\in S,T\not=0,d|\gcd(T)}(-1)^{|T|+1}
设d能整除S中的cnt个数，那么这个东西就是：

\sum\limits_{i=1}^{cnt}C_{cnt}^i(-1)^{i+1}=[cnt>0]

于是ans=\prod\limits_{\exists i\in 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;
}