bzoj5019: [Snoi2017]遗失的答案

Description

小皮球在计算出答案之后，买了一堆皮肤，他心里很开心，但是一不小心，就忘记自己买了哪些皮肤了。==|||万

幸的是，他还记得他把所有皮肤按照1～N来编号，他买来的那些皮肤的编号（他至少买了一款皮肤），最大公约数

是G，最小公倍数是L。现在，有Q组询问，每组询问输入一个数字X，请你告诉小皮球，有多少种合法的购买方案中

，购买了皮肤X？因为答案太大了，所以你只需要输出答案mod1000000007即可。

Input

第一行，三个数字N,G,L，如题意所示。

第二行，一个数字Q，表示询问个数。

第三行，Q个数字，表示每个询问所问的X。

N,G,L≤10^8,Q≤10^5,1≤X≤10^8

Output

对于每一组询问，在一行中单独输出一个整数，表示这个询问的答案。

如果L%G非零则无解，将L的每个质因子看作一维，只有每维都取到最小（L中对应质数的次数）和最大幂次（G中对应质数的次数），才能得到对应的G和L，状压表示每一维的质因数次数是否取到最小/大值，可以选的数一定每维幂次在最小值和最大值之间，这样的数很少，在数据范围内不超过800个，分治dp得出某个数不选的方案数，用总方案数减去即得到某个数必选的方案数。时间复杂度为O((L的约数个数)*log(L的约数个数)*4^(L的不同质因子个数))

#include<bits/stdc++.h>

typedef int mat[][];

const int P=1e9+;

int _(){

    int x=,c=getchar();

    while(c<)c=getchar();

    while(c>)x=x*+c-,c=getchar();

    return x;

}

int n,g,l,qp,mx,fs[],tg[],tl[],fp=,ans[];

inline void inc(int&a,int b){a+=b-P,a+=a>>&P;}

struct dat{

    int v,s1,s2;

    bool operator<(const dat&w)const{return v<w.v;}

    void trans(mat a){

        for(int i=mx-;i>=;--i){

            int*m1=a[i],*m2=a[i|s1];

            for(int j=mx-;j>=;--j)inc(m2[j|s2],m1[j]);

        }

    }

}vs[];

int vp=;

void f1(int x){

    for(int i=;i*i<=x;++i)if(x%i==){

        do x/=i;while(x%i==);

        fs[fp++]=i;

    }

    if(x>)fs[fp++]=x;

}

void f2(int x,int*t){

    for(int i=;i<fp;++i)for(;x%fs[i]==;x/=fs[i],++t[i]);

}

void dfs(int w,int v,int s1,int s2){

    if(w==fp){

        if(v<=n)vs[++vp]=(dat){v,s1,s2};

        return;

    }

    for(int i=;i<=tl[w];++i,v*=fs[w]){

        if(i>=tg[w])dfs(w+,v,s1|(i==tg[w])<<w,s2|(i==tl[w])<<w);

    }

}

mat F[];

int Fp=,all;

void cpy(){

    for(int i=;i<mx;++i)memcpy(F[Fp+][i],F[Fp][i],sizeof(int)*mx);

    ++Fp;

}

void solve(int L,int R){

    if(L==R){

        if(R==){

            cpy();

            vs[].trans(F[Fp]);

            all=F[Fp][mx-][mx-];

            --Fp;

        }

        ans[L]=((all-F[Fp][mx-][mx-])%P+P)%P;

        return;

    }

    int M=L+R>>;

    cpy();

    for(int i=M+;i<=R;++i)vs[i].trans(F[Fp]);

    solve(L,M);

    --Fp;

    cpy();

    for(int i=L;i<=M;++i)vs[i].trans(F[Fp]);

    solve(M+,R);

    --Fp;

}

void nos(){

    while(qp--)puts("");

    exit();

}

int main(){

    n=_(),g=_(),l=_(),qp=_();

    f1(g),f1(l);

    std::sort(fs,fs+fp);

    fp=std::unique(fs,fs+fp)-fs;

    f2(g,tg),f2(l,tl);

    if(n<g)nos();

    for(int i=;i<fp;++i)if(tg[i]>tl[i])nos();

    dfs(,,,);

    std::sort(vs+,vs+vp+);

    mx=<<fp;

    F[][][]=;

    solve(,vp);

    while(qp--){

        int x=_(),w=std::lower_bound(vs+,vs+vp+,(dat){x})-vs;

        if(w<=vp&&vs[w].v==x)printf("%d\n",ans[w]);

        else puts("");

    }

    return ;

}

巴特西

bzoj5019: [Snoi2017]遗失的答案

Description

Input

Output

最新文章

热门文章