题目分析

首先有一个结论:$gcd(fib(a_i))= fib(gcd(a_i))$,可以尝试使用辗转相减球 gcd 的方法证明一下。(boshi: 可以证,但没必要)

然后 $lcm$是个什么玩意呢?对于一个指定的质因数 $p$,假设 $a_i$的质因数 $p$的次数为 $c_i$,则他们的 lcm 的 $p$的次数为 $max(c_i)$,gcd 的 $p$的次数为 $min(c_i)$。看到这里,可以考虑 Max-Min 容斥(又称 Max-Min 反演),最后可以得到:

$$lcm(fib(S))=\prod_{T \subset S,T \not= \emptyset} fib(gcd(T))^{(-1)^{|T|+1}}$$

假设 $fib(x)$的正数幂大小为 $c_1$,负数幂绝对值大小为 $c_2$,则我们只要把所有 $fib(x)^{c_1-c_2}$乘起来即可。

怎么求呢?以求 $c_1$为例,只要用 $O(n \ln n)$的时间求出 $x$的倍数有多少个,则知 $gcd$是 $x$的倍数,且集合大小为奇数的集合有多少个,设为 $f(x)$个。设 $gcd$是 $x$且集合大小为奇数的集合有 $g(x)$个,则有:

$$f(x)=\sum_{x|d} g(d)$$

莫比乌斯反演一下:

$$g(x)=\sum_{x|d} \mu(\frac{x}{d})f(d)$$

求 $g(x)$也是 $O(n \ln n)$的,完美!

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int mod=1000000007,N=1000000;
int n,tot,ans=1;
int a[N+5],b[N+5],f[N+5],mu[N+5],pri[N+5],is[N+5],c[N+5];

int ksm(int x,int y,int p) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%p) if(y&1) re=1LL*re*x%p;
    return re;
}
void prework() {
    f[1]=1;for(RI i=2;i<=N;++i) f[i]=(f[i-1]+f[i-2])%mod;
    for(RI i=1;i<=N;++i)
        for(RI j=i;j<=N;j+=i) b[i]=b[i]+a[j];
    mu[1]=1;
    for(RI i=2;i<=N;++i) {
        if(!is[i]) pri[++tot]=i,mu[i]=-1;
        for(RI j=1;j<=tot&&pri[j]*i<=N;++j) {
            is[pri[j]*i]=1;
            if(i%pri[j]==0) break;
            else mu[pri[j]*i]=-mu[i];
        }
    }
}
void getc1() {
    for(RI i=1;i<=N;++i) if(b[i]) b[i]=ksm(2,b[i]-1,mod-1);
    for(RI i=1;i<=N;++i)
        for(RI j=i;j<=N;j+=i)
            c[i]=(1LL*c[i]+1LL*mu[j/i]*b[j]+mod-1)%(mod-1);
}
void getc2() {
    for(RI i=1;i<=N;++i) if(b[i]) --b[i];
    for(RI i=1;i<=N;++i)
        for(RI j=i;j<=N;j+=i)
            c[i]=(1LL*c[i]-1LL*mu[j/i]*b[j]+mod-1)%(mod-1);
    for(RI i=1;i<=N;++i) c[i]=(c[i]+mod-1)%(mod-1);
}

int main()
{
    n=read();
    for(RI i=1;i<=n;++i) ++a[read()];
    prework();
    getc1(),getc2();
    for(RI i=1;i<=N;++i) ans=1LL*ans*ksm(f[i],c[i],mod)%mod;
    printf("%d\n",ans);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

4 条评论

XZYAFO · 2018年12月24日 8:04 下午

我想让贵方成为 K-XZY 名誉站长,以后站点就叫 666-FKL
不知贵方意向如何

    litble · 2018年12月24日 8:08 下午

    我方的意向是若贵方给我方升权限就可以考虑

      XZYAFO · 2018年12月24日 8:28 下午

      我方在博客里写了丢人日记因此不能提升权限,贵方成为名誉站长对双方都有好处,我方可以蹭巨佬热度,贵方可以。。。可以。。。可以名誉,岂不美哉?

        litble · 2018年12月24日 9:00 下午

        我方被贵方 FAKE,于我方有百害而无一利,故拒绝

发表评论

电子邮件地址不会被公开。 必填项已用*标注