自动搬运

查看原文

来自洛谷，原作者为

	ViXbob **

搬运于2025-08-24 22:10:03，当前版本为作者最后更新于2019-05-16 11:25:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

滋磁去我的博客看啊

妙妙题..

首先判掉$L$不是$G$的倍数的情况.

然后先来考虑一下没有一定要包含$X$的这个限制的情况:

对于$L$的每个质因子$p_i$,设$\text{MxP}(p_i,x)=k(p_i^k\mid x,p_i^{k+1}\not\mid x)$;

设$m$为$L$不同的质因子的个数.

我就是要选出来一些数使得对于每个质因子$p_i$,至少存在一个数$x$使得$\text{MxP}(p_i,x)=\text{MxP}(p_i,L)$, 至少存在一个数$y$使得$\text{MxP}(p_i,x)=\text{MxP}(p_i,G)$.

那么我们把每个数都看成一个长为$2m$的$01$串,记录它对于每一个质因子$p_i$,是否满足$\text{MxP}(p_i,x)=\text{MxP}(p_i,L)$, 或满足$\text{MxP}(p_i,x)=\text{MxP}(p_i,G)$.

那么我们最后就是要找若干个数使得它们或出来是一个长为$2m$的全是$1$的串.因为$m \le 8$,这道题就变得可做多了.

然后这个是可以$\text{FWT}$的.对于$X$的限制,记一个前后缀$\text{FWT}$的结果就好了,但是复杂度不太对.

我们可以考虑容斥:

我就是要求找出来一些数使它们或为全集,设:$f(S)$表示或出来为$S$的方案数,

那么$g(S)=2^{con(S)}$($con(S)$为$S$的子集的个数).然后这个就可以直接子集反演了:

再考虑一下有$X$的限制.就是我们或出来的只能是$X$的超集.设$f(S)$表示或出来的数为$S$并且一定选中了$X$的方案数.这里的$g(S)$和上述的含义一样.只是$g(S)=[X\subseteq S]2^{con(S)-1}$.减一就是我们去掉没选$X$的这种情况.然后容斥和上面是一样的.

虽然询问有很多但是不同的$01$状态只有$2^{2m}$,并且我们每次容斥时只用枚举$X$的超集就好了,所以复杂度为$O(3^{2m})$.($m\le 8$)

代码:

/*
 * 2257.cpp
 * This file is part of 2257
 *
 * Copyright (C) 2019 - ViXbob
 *
 * 2257 is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * 2257 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with 2257. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * There is no end though there is a start in space. ---Infinity.
 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
 * Only the person who was wisdom can read the most foolish one from the history.
 * The fish that lives in the sea doesn't know the world in the land.
 * It also ruins and goes if they have wisdom.
 * It is funnier that man exceeds the speed of light than fish start living in the land.
 * It can be said that this is an final ultimatum from the god to the people who can fight.
 *
 * Steins;Gate
 */
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int n, G, L, Q, x, pow2[maxn], U, l[maxn], r[maxn], siz[maxn], N, ans[1 << 17];
vector<pair<int, int> > facL, data;

inline int read() {
	char ch = getchar(); int u = 0, f = 1;
	while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
	while(isdigit(ch))  { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

inline void GetFac(int x, vector<pair<int, int> > &fac) {
	for(int i = 2; i * i <= x; i++) if(x % i == 0) {
		int cnt = 0;
		while(x % i == 0) x /= i, cnt++;
		fac.pb(mp(i, cnt));
	}
	if(x != 1) fac.pb(mp(x, 1));
}

inline void Binout(int S) {
	stack<int> st;
	while(S) st.push(S & 1), S >>= 1;
	rep(i, 1, N - st.size()) putchar('0');
	while(st.size()) putchar(st.top() + '0'), st.pop();
	putchar('\n');
}

inline pair<int, int> GetState(int x) {
	int S = 0, y = x;
//	cerr << "------------------------" << endl;
//	cerr << "x = " << x << endl;
	rep(i, 0, SIZE(facL) - 1) {
		int cnt = 0;
		while(x % facL[i].first == 0) x /= facL[i].first, cnt++;
		S |= (cnt == l[i]) << i;
		S |= (cnt == r[i]) << i + SIZE(facL);
	}
//	Binout(S);
	return mp(y, S);
}

inline void PreSolve() {
	GetFac(L, facL);
	pow2[0] = 1; N = SIZE(facL) << 1; U = (1 << N) - 1;
	rep(i, 1, U) pow2[i] = pls(pow2[i - 1], pow2[i - 1]);
	rep(i, 0, SIZE(facL) - 1) {
		r[i] = facL[i].second;
		int x = G;
		while(x % facL[i].first == 0) l[i]++, x /= facL[i].first;
	}
//	rep(i, 0, SIZE(facL) - 1) cerr << "l[" << i << "] = " << l[i] << ", r[" << i << "] = " << r[i] << endl;
	for(int i = 1; 1ll * i * i <= L; i++) if(L % i == 0) {
		if(i % G == 0 && i <= n) data.pb(GetState(i));
		if(i * i != L && (L / i) % G == 0 && (L / i) <= n) data.pb(GetState(L / i));
	}
	sort(data.begin(), data.end());
	for(auto v : data) siz[v.second]++;
	rep(i, 0, N - 1) rep(S, 0, U) if(S >> i & 1) siz[S] += siz[S ^ (1 << i)];
//	rep(S, 0, U) cerr << "size[" << S << "] = " << siz[S] << endl;
}

inline int Solve(int x, int rnt = 0) {
	auto it = *lower_bound(data.begin(), data.end(), mp(x, 0));
	if(ans[it.second] != -1) return ans[it.second];
	int T = it.second, S = U ^ T; rnt = __builtin_popcount(T) & 1 ? dec(rnt, pow2[siz[T] - 1]) : pow2[siz[T] - 1];
	for(int S1 = S; S1; S1 = (S1 - 1) & S) 
		if(__builtin_popcount(S1 | T) & 1) rnt = dec(rnt, pow2[siz[S1 | T] - 1]);
		else rnt = pls(rnt, pow2[siz[S1 | T] - 1]);
	return ans[it.second] = rnt;
}

int main() {
//	freopen("1.in", "r", stdin);
//	freopen("my.out", "w", stdout);
	n = read(); G = read(); L = read(); Q = read();
	if(L % G) { rep(i, 1, Q) puts("0"); return 0; }
	PreSolve();
	memset(ans, -1, sizeof(ans));
	rep(i, 1, Q) {
		x = read();
		if(x % G != 0 || L % x != 0 || x > n) puts("0");
		else printf("%d\n", Solve(x));
	}
	return 0;
}
/*
2 * 3 * 5
1 2 3 4 5
1
2
2
0
2
*/