洛谷P4495 奇怪的背包 [HAOI2018] 数论

时间：2021-05-25 07:27:53

正解:数论+dp

解题报告:

传送门!

首先看到这题,跳无数次,自然而然可以想到之前考过好几次了的一个结论——如果只考虑无限放置i,它可以且仅可以跳到gcd(p,v[i])

举一反三一下,如果有多个i,表示成a[i]好了,那就一定是能跳到gcd(p,v[a[1]],v[a[2]],..,v[a[n]]),因为这个太长了后面单一个gcd就指的它

挺显然的这儿不证明了QAQ

然后这儿就相当于是问有多少种a[i]的方案能满足gcd|gcd(p,w)

然后因为多组询问,显然考虑能不能预处理一个f[i]:能表示出i的集合的个数

显然可以考虑先求f[i]:gcd恰好为i的集合个数,然后搞个f[i]=∑f[d](d|i),就求出来答案辣

然后现在就变成考虑怎么样求出前面那个意义下的f

考虑什么情况可能对f[i]有贡献?显然只有i的倍数才行

所以先统计出i的倍数的个数为cnt,那就有gcd为i的倍数的数就有2cnt-1个,这里应该能get?

但是要考虑去重昂,就因为我们统计的是gcd为i的倍数的个数,所以把所有是i的倍数的再减去就得到的是gcd=i的数量了

最后把那个f[i]=∑f[d](d|i)搞下就欧克

综上,这题就做完了

好像说得很潦草不好理解的样子,但反正没人看,我又懒得写了,就这样趴hhhh

如果居然有人看又没看懂在下面留言就成我再重新组织下语言重构这篇题解算了,,,

然后再瞎说下细节趴QAQ

首先因为p的范围是1e9,然后对p的所有约数都是要统计的,所以如果设数组就要开到1e9,所以显然考虑离散化一下,但是怎么离散化还是要记下name[i]=j表示i的离散化之后对应的值,就还是要开1e9的

所以有两种方案,一个是开个map,另一个是开两个name数组

因为我是开了两个nam数组而且map那个很无脑所以map那个我就不说了只大概港下name数组

就直接分类讨论,随便设定一个界限M,M的大小随意只要是能开得下数组又没太小就欧克

然后对d<=M的因数d直接放到name1[d]里存着,否则存到name2[p/d]

然后就做完了?应该没什么了,其实我觉得我讲得还是挺详细的来着,,,

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

#define il inline

#define gc getchar()

#define t(i) edge[i].to

#define mp make_pair

#define ri register int

#define rb register bool

#define rc register char

#define lb(x) lower_bound(st+1,st+st_cnt,x)-st

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=1e6+,mod=,M=;

int n,q,p,v[N],w[N],poww[N]={},divv[N],div_cnt,id1[M],id2[M],s[M],f[M];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch<'' || ch>''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il int gcd(ri gd,ri gs){return gs?gcd(gs,gd%gs):gd;}

il int ask_id(ri x){return x<=M?id1[x]:id2[p/x];}

int main()

{

//     freopen("4495.in","r",stdin);//freopen("4495.out","w",stdout);

    n=read();q=read();p=read();rp(i,,n)v[i]=gcd(read(),p);rp(i,,n)poww[i]=(poww[i-]<<)%mod;

    for(ri i=;i*i<=p;++i)if(!(p%i)){divv[++div_cnt]=i;if(i*i!=p)divv[++div_cnt]=p/i;}

    sort(divv+,divv++div_cnt);rp(i,,div_cnt)if(divv[i]<=M)id1[divv[i]]=i;else id2[p/divv[i]]=i;

    rp(i,,n)++s[ask_id(v[i])];

    my(i,div_cnt,)

    {

        ri tmp1=s[i],tmp2=;

        rp(j,i+,div_cnt)if(!(divv[j]%divv[i]))tmp2=(tmp2+f[j])%mod,tmp1+=s[j];

        f[i]=(poww[tmp1]--tmp2+mod)%mod;

    }

    my(i,div_cnt,)

        rp(j,,i-)if(!(divv[i]%divv[j]))f[i]=(f[i]+f[j])%mod;

    while(q--)printf("%d\n",f[ask_id(gcd(read(),p))]);

    return ;

}

最后放个代码趴!

相关文章