正题

题目链接:http://www.51nod.com/Challenge/Problem.html#problemId=1355

题目大意

定义\(f_i\)表示斐波那契的第\(i\)项，给出一个大小为\(n\)的集合\(S\)求\(lcm(f_S)\)

解题思路

如果每个质数的次数分开考虑，那么\(gcd\)就是次数取\(min\)，\(lcm\)就是次数取\(max\)，所以可以套用\(min-max\)容斥的式子

\[lcm(S)=\prod_{T\subseteq S}gcd(T)^{(-1)^{|T|+1}}
\]

然后因为\(gcd(f_x,f_y)=f_{gcd(x,y)}\)，那么这题的答案

\[lcm(f_S)=\prod_{T\subseteq S}f_{gcd(T)}^{(-1)^{|T|+1}}
\]

这个好像算起来很麻烦，我们可以分开考虑每个\(gcd\)的贡献。

定义\(f_n=\prod_{d|n}g_d\)

\[lcm(f_S)=\prod_{T\subseteq S}\left(\prod_{d|gcd(T)}g_d\right)^{(-1)^{|T|}+1}
\]

\[lcm(f_S)=\prod g_d^{\sum_{T\subseteq S}[d|gcd(T)](-1)^{|T|+1}}
\]

然后就是\(\sum_{T\subseteq S}[d|gcd(T)](-1)^{|T|+1}\)，因为没有了空集，这个东西其实就相当于\([\exists a_i\in S,d|a_i]\)。然后就可以直接枚举每个\(d\)来求答案了。

\[lcm(f_S)=\prod_{\exists a_i\in S,d|a_i} g_d
\]

考虑\(g\)怎么构造，我们有\(f_n=\prod_{d|n}g_d\)，直接移项就是\(g_n=f_n-\prod_{d|n,d\neq n}g_d\)就好了。

时间复杂度\(O(n\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=1e6+10,P=1e9+7;

ll n,m,g[N],ans;

bool v[N];

ll power(ll x,ll b){

    ll ans=1;

    while(b){

        if(b&1)ans=ans*x%P;

        x=x*x%P;b>>=1;

    }

    return ans;

}

signed main()

{

    scanf("%lld",&n);g[1]=ans=1;

    for(ll i=1;i<=n;i++){

        ll x;scanf("%lld",&x);

        m=max(m,x);v[x]=1;

    }

    for(ll i=2;i<=m;i++)g[i]=(g[i-1]+g[i-2])%P;

    for(ll i=1;i<=m;i++){

        ll inv=power(g[i],P-2);

        for(ll j=2*i;j<=m;j+=i)

            g[j]=g[j]*inv%P;

    }

    for(ll i=1;i<=m;i++){

        bool flag=0;

        for(ll j=i;j<=m;j+=i)

            if(v[j]){flag=1;break;}

        if(flag)ans=(ans*g[i])%P;

    }

    printf("%lld\n",ans);

    return 0;

}

巴特西

51nod1355-斐波那契的最小公倍数【min-max容斥】

正题

题目大意

解题思路

code

最新文章

热门文章