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

Upd2019.4.19

yy了一个新的做法
新的写法

之前的东西

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

很神奇的一个题
首先，我们通过打表可以得到一个结论
当满足递推式$f(n)=a\times f(n?1)+b\times (n?2)$
且满足$(a,b)=1$，$f(0)=0$时
有$gcd(f(x),f(y))=f(gcd(x,y))$
但是你发现，因为增长过快，因此表只可以验证到第10项。。第20项基本就爆了

现在有了gcd，怎么求lcm呢？
我们知道，lcm是每一个质因子次数取max，gcd是取min
于是我们可以min-max容斥一下
可以得到$$lcm(S)={\Pi }_{S^{\prime }?S}gcd(S^{\prime })\times (?1{)}^{|S^{\prime }|+1}$$
$S^{\prime }$不为空
这个式子看起来没法做。。
有一个很神仙的构造可以快速解决这个问题
为了方便，我们把式子写成
$$F(S)={\Pi }_{S^{\prime }?S}f(S^{\prime })\times (?1{)}^{|S^{\prime }|+1}$$
我们构造一个函数$g(x)$,使得$f(S^{\prime })={\Pi }_{d|gcd(S^{\prime })}g(d)$
于是可以得到
$$F(S)={\Pi }_{S^{\prime }?S}{\Pi }_{d|f(S^{\prime })g(d)}\times (?1{)}^{|S^{\prime }|+1}$$
根据套路，我们把$g(d)$提出来
$$F(S)=\Pi g(d{)}^{{\sum }_{S^{\prime }?S}{\sum }_{d|f(S^{\prime })}(?1{)}^{|S^{\prime }|+1}}$$
我们把是d的倍数看做一个新的集合$T$
你会发现，其实他就是T选奇数和偶数个的差
当然，不选空集
根据二项式定理，可以得到，如果为空，是0，否则都是1
因此，可以得到一个优秀的做法，就是只要有倍数，就乘上，否则跳过
g的话，从前往后筛就好了

时间复杂度是$O(MlogM)$的，$M$是最大的数字
喜闻乐见的低代码复杂度
CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
const LL N=1000005;
LL f[N];
LL Pow (LL x,LL y)
{
    if (y==1) return x;LL lalal=Pow(x,y>>1);lalal=lalal*lalal%MOD;if (y&1) lalal=lalal*x%MOD;return lalal;
}
LL g[N];
bool ok[N];
void Init (int n)
{
    f[0]=0;g[1]=f[1]=1;for (LL u=2;u<=n;u++) g[u]=f[u]=(f[u-1]+f[u-2])%MOD;for (LL u=1;u<=n;u++){
    LL Inv=Pow(g[u],MOD-2);for (LL i=u+u;i<=n;i+=u)	g[i]=g[i]*Inv%MOD;}
}
int main()
{
    Init(1000000);memset(ok,false,sizeof(ok));LL n;scanf("%lld",&n);for (LL u=1;u<=n;u++)	{
    LL x;scanf("%lld",&x);ok[x]=true;}LL ans=1;for (LL u=1;u<=1000000;u++){
    bool tf=false;for (LL i=u;i<=1000000;i=i+u)	tf=(tf|ok[i]);if (tf) ans=ans*g[u]%MOD;}printf("%lld\n",ans);return 0;
}