CodeForces 1562F Tubular Bells
告诉你 n，要你猜一个长度为 n 的正整数序列 {ai}，ai 两两不同，且存在 0≤l≤2×105−n 使得 ai∈(l,l+n]。
每次你可以向交互库询问 ? x y（x=y），交互库向你返回 lcm(ax,ay)。询问次数为 n+5000，其中 3≤n≤105。
我们先考虑 n 比较小的情况，这时候我们可以考虑到我们有那个 5000，我们考虑 n2 次询问。我们考虑利用一个柿子，也就是当 gcd(x,y)=1 时，gcd(lcm(x,z),lcm(y,z))=gcd(gcd(x,z)xz,gcd(y,z)yz)=z⋅gcd(gcd(x,z)x,gcd(y,z)y)=z，且有 ∀x,y∈N+，z∣gcd(lcm(x,z),lcm(y,z))。又 ∀n∈N+，gcd(n,n+1)=1。故当 n=4 时，我们只要令 ai=gcdj=ilcm(ai,aj) 即可。而当 n=3 时，我们发现最大的那个询问结果其实是两个最大的相乘，也即最小值为 ⌊ 查询得到的最大值⌋−1，且最小值的那个位置确定了，然后另外两个直接与最小值取 lcm 之后对比一下就也确定了。
这种情况下，询问次数是 2n⋅(n−1)，而 2n⋅(n−1)≤5000+n 正好解得 n≤100。
这样我们就解决了 n≤100 的情况，我们考虑 n 更大的时候。首先我们会考虑到我们能否找到一个素数 p，且这个素数能尽量大，最好能保证 lcm(p,ai)=p⋅ai。我们考虑能否找到 p≥2n，这样的话除了有一个 ai=2p 可能会存在 lcm(p,ai)=2p。之外，其余的 ai 都能直接使用 ai=plcm(p,ai) 得到。因此我们可以先把除了 lcm 为 2p 的位置留下，其余位置查询之后，换一个不是 2 的素数判断那个位置是 2 还是 2p。我们考虑时候有这样的两个素数，大概估计 π(n))=lnnn，当 n 较大的时候素数密度是越来越疏的。而 π(105)−π(105−100)=7.93，也就是说应该是足够的，而事实证明当 n≥100 的时候确实是足够的。
然后我们考虑怎么找素数，我们考虑随机找一些位置并尝试将其确定下来。我们先大概看看应该需要找多少个位置，我们考虑由于素数密度越来越疏，我们就当是最大值是 105，于是素数密度为 ρ(n)=nπ(105)−π(105−n)，考虑到越往里素数越密，我们仍然认为选到素数的概率最小值为 ρ(100)=0.08，其实发现还是挺大的。然后我们考虑如何确定一个数，我们仍然用上面 n2 暴力的思路，我们考虑所随机几个数与要确定的这个数进行 lcm，我们考虑随机两个数的素数概率为多大，我们令概率为 P，那么我们发现如果随机两个数 gcd 为 i(i≥2,i∈N+) 的概率为 i2P，也就是要在 in 的空间里找到的 gcd 为 1 的方案然后把区间拉长 i 倍，由于是两个数所以除了 i2。于是我们有 P=1−∑i=lri2P也即 P=1+∑i=lri211，期望尝试 1+∑i=lri21 次，并不是一个很大的数。而我们又考虑生日悖论，因为我们是随机抽取多个数字，然后只要有其中两个 gcd 为 1 即可，所以理论上即使是非洲酋长也应该是能过的。
由于附赠了 5000 次询问次数，所以我们考虑选 249 个数，每个数抽 20 个数与之 lcm 之后求 gcd。剩下的 20 次其实是给前面说的那个 2p 的特殊情况留的。然后最后我们一遍 O(n) 询问即可。
由于交互题写了很多调试语句所以代码可能有点小长 qaq
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
| typedef long long LL;
int n;
LL ask(int x, int y) {
assert(1 <= x && x <= n && 1 <= y && y <= n);
std::cout << "? " << x << ' ' << y << std::endl;
std::cout.flush();
LL ans;
std::cin >> ans;
return ans;
}
namespace solve_small {
const int maxn = 105;
LL lcm[maxn][maxn];
void solve() {
memset(lcm, 0, sizeof(lcm));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
lcm[i][j] = lcm[j][i] = ask(i, j);
}
}
std::pair<int, int> idans(0, 0);
if (n == 3) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if (lcm[i][j] > lcm[idans.first][idans.second]) {
idans = std::make_pair(i, j);
}
}
}
std::vector<int> ANS(4);
ANS[idans.first] = sqrt(lcm[idans.first][idans.second]);
ANS[idans.second] = ANS[idans.first] + 1;
ANS[6 - idans.first - idans.second] = ANS[idans.first] - 1;
if ((LL) ANS[idans.first] * ANS[6 - idans.first - idans.second]
/ std::__gcd(ANS[idans.first], ANS[6 - idans.first - idans.second])
!= lcm[idans.first][6 - idans.first - idans.second]) {
std::swap(ANS[idans.first], ANS[idans.second]);
}
std::cout << "! ";
for (int i = 1; i <= 3; ++i) {
std::cout << ANS[i] << ' ';
}
std::cout << std::endl;
std::cout.flush();
} else {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
lcm[i][i] = std::__gcd(lcm[i][i], lcm[i][j]);
}
}
std::cout << "! ";
for (int i = 1; i <= n; ++i) {
std::cout << lcm[i][i] << ' ';
}
std::cout << std::endl;
std::cout.flush();
}
}
}
namespace solve_large {
struct debug {
int n;
std::vector<int> alb;
LL ask(int x, int y) {
return (LL) alb[x - 1] * alb[y - 1] / std::__gcd(alb[x - 1], alb[y - 1]);
}
debug() {
std::ifstream fin("a.in");
fin >> n;
for (int i = 1; i <= n; ++i) {
int xx;
fin >> xx;
alb.push_back(xx);
}
}
} deb;
#ifdef Debug
#define ask(x, y) deb.ask(x, y)
#endif
const int maxn = 200005;
LL ans[maxn];
int np[maxn];
std::mt19937 rnd(20030211u);
void Euler(const int n = 200000) {
std::vector<int> prime;
prime.clear();
for (int i = 2; i <= n; ++i) {
if (!np[i]) {
prime.push_back(i);
}
for (unsigned j = 0; j < prime.size() && (LL) i * prime[j] <= n; ++j) {
np[i * prime[j]] = true;
if (!(i % prime[j])) {
break;
}
}
}
}
void solve() {
std::vector<int> id;
id.clear();
for (int i = 1; i <= n; ++i) {
ans[i] = 0;
id.push_back(i);
}
std::shuffle(id.begin(), id.end(), rnd);
int qd = 0;
for (int i = 1; i <= 249 && i <= n; ++i) {
qd = id[i - 1];
for (int j = 1; j <= 20; ++j) {
int wz = rnd() % n + 1;
while (wz == qd) {
wz = rnd() % n + 1;
}
ans[qd] = std::__gcd(ask(qd, wz), ans[qd]);
if (ans[qd] <= 200000 && ans[qd] && !np[ans[qd]]) {
break;
}
}
if (ans[qd] && !np[ans[qd]] && ((ans[qd] << 1) > n)) {
break;
}
}
assert(ans[qd] <= 200000 && ans[qd] && !np[ans[qd]] && ((ans[qd] << 1) > n));
for (int i = 1; i <= n; ++i) {
if (!ans[i]) {
ans[i] = ask(i, qd) / ans[qd];
}
}
LL mx = 0;
int idd = 0;
for (int i = 1; i <= n; ++i) {
if (!np[ans[i]] && ans[i] >= mx) {
mx = ans[i];
idd = i;
}
}
for (int i = 1; i <= n; ++i) {
if (ans[i] == 2) {
ans[i] = ask(i, idd) / mx;
}
}
#ifndef Debug
std::cout << "! ";
#endif
for (int i = 1; i <= n; ++i) {
std::cout << ans[i] << ' ';
}
std::cout << std::endl;
std::cout.flush();
}
#ifdef Debug
#undef ask(x, y) deb.ask(x, y)
#endif
}
void solve() {
#ifndef Debug
std::cin >> n;
#else
n = solve_large::deb.n;
freopen("a.out", "w", stdout);
std::cout << n << std::endl;
#endif
if (n <= 100) {
solve_small::solve();
} else {
solve_large::solve();
}
}
int main() {
solve_large::Euler();
int T;
#ifndef Debug
std::cin >> T;
#else
T = 1;
#endif
while (T--) {
solve();
}
return 0;
}
|
