【BZOJ5302】[HAOI2018]奇怪的背包（动态规划，容斥原理）

【BZOJ5302】[HAOI2018]奇怪的背包（动态规划，容斥原理）

题面

BZOJ
洛谷

题解

为啥泥萌做法和我都不一样啊
一个重量为(V_i)的物品，可以放出所有(gcd(V_i,P))的重量，而多个物品也只要(gcd)就好了。
现在的问题转变成了有多少个集合(S)，满足(S+{P})中所有数的(gcd)是(w)的因数。那么实际上就是直接令(a[i]'=gcd(a[i],P))，然后选出一个集合使得它是(gcd(P,w))的因数。
考虑对于(P)的每个因数预处理答案，不记得在哪里看到的，当(P)较大的时候，其约数个数是(P^{frac{1}{3}})级别，那么在这里就可以暴力把所有因数算出来之后(O(sigma^2))计算，即先统计有多少个(a[i]')是当前(d)的倍数，那么贡献是(2^{s}-1)，然后容斥减去所有(d)的倍数的答案就是(gcd)为(d)的答案。然后再(O(sigma^2))的计算约数和就好了。
这样子复杂度大概是(O((n+Q)logP+sigma(P)^2))，前面那个(log)来自于(gcd)的复杂度。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 1000000007
#define MAX 1000100
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,Q,P,a[MAX],bin[MAX];
const int blk=50000;
int w[blk],tot,id1[blk],id2[blk],f[blk],s[blk];
int ID(int x){return x<blk?id1[x]:id2[P/x];}
int S[blk],top;
int main()
{
	n=read();Q=read();P=read();
	for(int i=1;i<=n;++i)a[i]=__gcd(read(),P);
	bin[0]=1;for(int i=1;i<=n;++i)bin[i]=(bin[i-1]<<1)%MOD;
	for(int i=1;i*i<=P;++i)
		if(P%i==0)
		{
			w[++tot]=i;
			if(P/i!=i)w[++tot]=P/i;
		}
	sort(&w[1],&w[tot+1]);
	for(int i=1;i<=tot;++i)
		if(w[i]<blk)id1[w[i]]=i;
		else id2[P/w[i]]=i;
	for(int i=1;i<=n;++i)s[ID(a[i])]+=1;
	for(int i=tot;i;--i)
	{
		int cnt=0;top=0;
		for(int j=i;j<=tot;++j)
			if(w[j]%w[i]==0)S[++top]=j,cnt+=s[j];
		f[i]=bin[cnt]-1;
		for(int j=2;j<=top;++j)f[i]=(f[i]+MOD-f[S[j]])%MOD;
	}
	for(int i=tot;i;--i)
		for(int j=1;j<i;++j)
			if(w[i]%w[j]==0)f[i]=(f[i]+f[j])%MOD;
	while(Q--)
	{
		int d=__gcd(read(),P);
		printf("%d
",f[ID(d)]);
	}
	return 0;
}