ShanLunjiaJian的blog

ShanLunjiaJian的blog

仰天大笑出门去,我辈就是蓬蒿人

CF585E Present for Vitalik the Philatelist 题解

posted on 2021-07-09 16:56:48 | under 题解 |

为什么大家都要莫反啊/dk,呃不过我这个可能跟莫反有本质相同的地方?

你发现这个面值少的可怜只有1e7,这是为什么?

gcd卷积。考虑我们先把所有数卷起来得到一个 $f_i$ 表示取若干数 $\gcd$ 为 $i$ 的方案数 的序列,然后剔除掉 $f_1$ 表示这部分 $\gcd>1$ ,再卷上所有数(也就是 $c_i$ 表示 $i$ 的个数),取第 $1$ 位就是答案。

现在问题是怎么把所有数卷起来。考虑类似于某个经典题的做法,$z+z^x$ 这样的东西fmt一下乘进答案,就相当于给 $x$ 的因数全都乘上 $2$ ,所以可以打一个标记,然后用fmt来推这个标记,然后再逆fmt回去。这就做完了,复杂度 $O(n+v\log\log v)$ 。

呃为什么点乘上 $z+z^x$ fmt的结果,是把 $x$ 的因数都乘 $2$ ?考虑对这个东西做fmt,就是先给所有数 $+1$ ,然后给 $x$ 的因数 $+1$ ,那么某个东西跟这个点乘起来,不就是把它里面 $x$ 的因数全部乘 $2$ 吗(

#include<stdio.h>

const int P=1e9+7,V=1e2;
inline void mod(int &x){ if(x>=P) x-=P; }

int prime[1000002],pcnt;
bool b[10000002];
inline void sieve(int n)
{
    for(int i=2;i<=V;i++)
    {
        if(!b[i]) prime[++pcnt]=i;
        for(int j=1;j<=pcnt&&i*prime[j]<=V;j++)
        {
            b[i*prime[j]]=1;
            if(!(i%prime[j])) break;
        }
    }
}

int n,c[10000002],f[10000002];

inline void fmt(int n,int *A)//dirichlet suffix sum
{
    for(int i=1;i<=pcnt;i++)
        for(int j=V/prime[i];j>0;j--)
            mod(A[j]+=A[prime[i]*j]);
}
inline void ifmt(int n,int *A)
{
    for(int i=1;i<=pcnt;i++)
        for(int j=1;prime[i]*j<=V;j++)
            mod(A[j]+=P-A[prime[i]*j]);
}

int main()
{
    scanf("%d",&n);
    sieve(V);
    for(int i=1;i<=V;i++) f[i]=1;//f[1]=1,fmt(V,f,1)
    for(int i=1,x;i<=n;i++) scanf("%d",&x),c[x]++,mod(f[x]*=2);

    for(int i=1;i<=pcnt;i++)
        for(int j=V/prime[i];j>0;j--)
            f[j]=(long long)f[prime[i]*j]*f[j]%P;
    for(int i=2;i<=V;i++) mod(f[i]+=P-1);
    ifmt(V,f);
    f[1]=0;
    fmt(V,f);

    fmt(V,c);
    for(int i=1;i<=V;i++) f[i]=(long long)f[i]*c[i]%P;
    ifmt(V,f);
    printf("%d\n",f[1]);
    return 0;
}