给出n,G,Ln, G, L,有qq次询问。每次给出xx,问有多少种选数方案满足:

  1. 数字在[1,n][1, n]内,不重复,且必须选xx

  2. 最大公约数为GG,最小公倍数为LL

答案对109+710^9 + 7取模

n,G,L,x108,q105n, G, L,x \le 10^8, q\le 10^5

LOJ 2257

Solution

首先预处理出所有满足是LL约数且是GG倍数的数,最多只有768768

注意到gcd\gcdlcm\mathrm{lcm}操作实际上就是在每个质因数指数上的min\minmax\max,而10810^8内质因数数量最多的数也只有88个质因数,于是可以对于每个数用一个1616位二进制数记录它的每个质因数的指数是否等于限制的min\minmax\max,问题转化为选择子集按位或为全集的方案数

考虑容斥,钦定某些位置不选,剩下的位置任意,答案为S(1)S2sum(S)\sum_{S}(-1)^{|S|} 2^{sum(S)}

其中sum(S)sum(S)表示有多少个数是SS的子集,用高维前缀和预处理即可

原题要求强制某个数被选择的方案,只需要对每个数计算删掉它之后的方案,再用总方案减去即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 1e3;
const int MAXS = 1 << 16;
const int MOD = 1e9 + 7;

inline void ADD (int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

int N, G, L;
int pw[MAXN + 5];

vector <int> A;
vector <int> key, Min, Max;

inline void divide (int res)
{
for (int i = 2; i * i <= res; ++i) if (!(res % i))
{
int cnt = 0;
while (!(res % i)) ++cnt, res /= i;
key.pb (i);
}
if (res > 1) key.pb (res);
Min.resize (key.size());
Max.resize (key.size());
}

int S[MAXN + 5];

inline void Init ()
{
pw[0] = 1;
for (int i = 1; i <= MAXN; ++i) pw[i] = (LL) pw[i - 1] * 2 % MOD;

for (int i = 1, M = sqrt (L); i <= M; ++i) if (!(L % i))
{
if (i <= N && !(i % G)) A.pb (i);
if (i * i != L && L / i <= N && !((L / i) % G)) A.pb (L / i);
}

divide (L);

for (int i = 0; i < key.size(); ++i)
{
int x = key[i], res = L;
while (!(res % x)) ++Max[i], res /= x;
res = G;
while (!(res % x)) ++Min[i], res /= x;
}
}

inline void DP (int *A)
{
int all = (1 << (2 * key.size())) - 1;
for (int i = 0; i < 2 * key.size(); ++i)
for (int j = 0; j <= all; ++j) if (j >> i & 1)
A[j] += A[j ^ (1 << i)];
}

inline int calc (int *A)
{
int all = (1 << (2 * key.size())) - 1, ans = 0;
for (int i = 0; i <= all; ++i)
{
if (__builtin_popcount(i) & 1) ADD (ans, MOD - pw[A[all ^ i]]);
else ADD (ans, pw[A[all ^ i]]);
}
return ans;
}

inline void Solve ()
{
Init ();

for (int i = 0; i < A.size(); ++i)
{
for (int j = 0; j < key.size(); ++j)
{
int x = key[j], res = A[i], cnt = 0;
while (!(res % x)) ++cnt, res /= x;
if (cnt == Min[j]) S[i] |= 1 << j;
if (cnt == Max[j]) S[i] |= 1 << (j + key.size());
}
}

static int F[MAXS + 5];
static map <int, int> Ans;

for (int i = 0; i < A.size(); ++i) ++F[S[i]];
DP (F);
int sum = calc (F);

for (int i = 0; i < A.size(); ++i)
{
for (int j = 0, all = (1 << (2 * key.size())) - 1; j <= all; ++j) F[j] = 0;
for (int j = 0; j < A.size(); ++j) if (i != j) ++F[S[j]];
DP (F);
Ans[A[i]] = (sum - calc (F) + MOD) % MOD;
}

int Q = read<int>();
while (Q--) printf("%d\n", Ans[read<int>()]);
}

inline void Input ()
{
N = read<int>(), G = read<int>(), L = read<int>();
}

int main ()
{

#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}