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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
| 我们被要求：给定问题描述，求最小的n满足g(n) >= 10^4。用户之前尝试用某种方法计算给定质因数指数的分布的最大层宽度。用户给出了一些代码片段和输出，最后要求“请给我cpp实现代码”。
我们需要理解问题：对于正整数n，以其约数为顶点构造图。两个顶点a<b，如果b/a是质数，则连接。顶点n在第0层，距离n为k的顶点在第k层。g(n)是图中任意一层的顶点数的最大值。已知g(5040)=12。求最小的n满足g(n) >= 10^4。
这是一个经典问题。根据描述，这其实就是n的除数图（divisor graph），边连接如果商是质数。层数是质因子总指数之和。每一层的顶点数等价于从n的质因数分解开始，逐步去掉质因数的方式数量。实际上，g(n)是n的所有约数按照它们素因子总指数的分布：如果我们对n的每个素因子独立考虑，第k层就是从总指数和m中减掉k个质因子（每次选一个质因子减1）。这相当于多项式系数：如果n = p1^a1 * p2^a2 * ... * pk^ak，则第k层的顶点数等于从指数状态(a1, a2, ..., ak)走k步到达(0,0,...,0)的路径数，或者等价于将k个不可区分的步骤分配给各个质因子，每个质因子减少的步数不超过ai。实际上，由于图的层数是距离n的距离，所以从n开始每次除以一个质因子，相当于降低某个指数1。因此到达某个约数所需的步数是 sum (ai - bi)，其中bi是约数的指数。所以第k层包含所有指数和为 sum(ai) - k 的约数。这个数量等于多项式 (1 + x + x^2 + ... + x^{a1}) ... (1 + x + ... + x^{ak}) 展开中 x^{sum(ai)-k} 的系数。由于对称性，它就是 x^k 的系数。所以 g(n) = max_{k} [x^k] ∏_{i=1}^{r} (1 + x + ... + x^{a_i})。
我们需要找到最小的n使得这个最大值 >= 10000。
用户尝试的代码是枚举指数分布，计算组合数。他使用了16个相同的指数16的情况，最大层宽度为50101。也许他在探索什么样的指数组合能达到较大的最大层宽度，并希望得到最终解。
问题：g(n) >= 10^4，已知g(5040)=12。5040 = 2^4 * 3^2 * 5 * 7，指数为4,2,1,1。最大层宽度12。
我们需要求最小的n使得g(n) >= 10000。
这本质上是一个组合最优化问题：给定一个多重集指数{a_i}，最大化多项式系数，并且使得n尽可能小。n是 ∏ p_i^{a_i}，其中p_i是递增的质数。我们要最小化n，但受到g(n) >= 10000。显然我们需要尝试不同的质因子数量和指数分配，找到符合条件的n，并取最小。
但是用户说“因为本题数字不大，所以可以考虑直接暴力枚举所有数字的出现次数”，并展示了两个例子：指数全为16（16个16？）。他说“16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1”得到对称分布，最大16。所以他在尝试枚举。
我们需要给出最终的C++代码来求解这个具体问题：求最小的n满足g(n) >= 10000。
我们可以设计算法：枚举指数向量（非增序），计算对应的多项式系数的最大值。同时计算对应的n（使用前r个质数），记录满足条件的最小n。
由于问题是确定的，我们可以用程序搜索。可能搜索空间：指数和不能太大；我们需要最大系数 >= 10000。对于固定的总指数S = sum a_i，最大系数在分布尽可能均匀时最大。对于10000，总指数不需要太大。比如例子中16个16总指数256，最大系数5万。我们需要最小n，所以要用尽量小的质数，且尽量少的指数和？我们要在满足最大系数>=10000的前提下，最小化 n = ∏ p_i^{a_i}，p_i按顺序分配（p1=2, p2=3, ...）。注意指数可以排序，大的指数应该分配给小的质数以最小化n。所以我们只需考虑非增的指数序列a1 >= a2 >= ... >= ak > 0。
我们可以枚举所有可能的指数向量，计算多项式的最大系数，如果>=10000，计算n，更新最小值。
枚举范围：指数总和不会太大。估计一下：如果只有一种质数，指数a，最大系数是1（只有一层有1个顶点）。两种质数：指数a,b，多项式为 (1+x+...+x^a)(1+x+...+x^b)，最大系数约为 min(a,b)+1（如果a,b接近）。要达到10000，需要 a,b 约10000，n = 2^10000 * 3^10000 巨大。多种质数，总指数可以降低很多。例如指数为 3,3,3,3（四个3）: (1+x+x^2+x^3)^4，最大系数？展开最大项系数是 C(4+4-1, ...?) 我们可以算一下。要达到10000，可能需要更多更小的指数。已知g(5040)=12，指数4,2,1,1最大12。用户给出了16个16得到5万。所以我们需要找到精确最小值。
这类问题在Project Euler中可能是第XXX题？这是Project Euler 268? 不对，268是关于多项式系数的。我记得Project Euler有一道题：求最小的n使得除数图中最大层宽度超过10^4？可能是PE第几百道？实际上是Project Euler Problem 110还是什么的扩展？等等，有“约数图宽度”这道题可能是Project Euler problem 485? 不是。我在哪里见过“约数图”这个概念。可能是某些OJ上的题目。无论如何，我们可以写程序搜索。
由于要写代码，且用户要求“请给我cpp实现代码”，我需要给出完整的可运行C++程序，该程序计算出答案并输出。
我应提供解决方案，并说明逻辑。
我需要确保代码正确高效。可能的算法：
预生成质数列表。
递归枚举非增指数序列，限制总指数和或最大系数？因为我们需要最小化n，在搜索过程中，可以计算当前部分乘积n，剪枝。
对于每个指数序列，计算多项式系数最大值。可以用DP：dp[i][j]表示前i个因子，次数和为j的系数。由于总指数和最多可能几十或几百（估计一下：为了达到10000，需要一些指数；16个16总和256，最大值5万。也许总指数和100左右就够）。可以使用动态规划计算最大系数，同时找到最大值。
比较n，记录最小。
估计最大总和：我们可以近似，若指数全相等为a，共k个，总和S=ka。多项式的最大系数近似为 (ka choose k/2?) 实际上多项式的系数服从正态分布。对于 (1+x+...+x^a)^k，均值为 k*a/2，方差 k * (a^2 - 1)/12? 最大值大约为 (a+1)^k / sqrt(2πσ^2)。为了得到10000，k不需要太大。
我们可以在枚举时，如果当前序列的部分最大系数的上界已经无法达到10000，则剪枝。或者简单暴力枚举有限空间。
另一个思路：我们可以使用BFS动态规划生成所有可能的指数序列和对应的n，类似寻找最小n使得某些条件成立。但是问题要求是“最小的满足g(n)>=10^4的n”。注意n必须是整数，约数图宽度仅取决于指数的多重集，与具体质数分配有关。最小的n必然将较大的指数分配给较小的质数。因此指数序列是非增的。
我可以写一个程序：
用递归生成非增指数序列a1>=a2>=...>=am>0，限制总指数和比如<=200（足够）。
对每个序列，计算多项式(1+x+...+x^{a_i})乘积的系数的最大值。使用DP（用vector< int >或bigint? 系数可能超过10^4，但int足够）。如果最大值>=10000，计算对应的n = ∏_{i=1}^m p_i^{a_i}，这里p_i是第i个质数（2,3,5,7,...）。因为指数非增，质数非降，乘积最小化符合要求。
记录最小n。
输出结果。
为了加速，可以按照n从小到大的顺序搜索？但枚举所有可能序列，计算n并取最小即可。状态空间多大？需要限制最大指数，最大质数个数。通过上界估计：假设我们最多考虑15个质数。a最大可能比如20。我们可以枚举所有总指数和<=300的可能。组合数可能很多，但可以完成。我们可以用DP提前计算多项式最大值，不需要每次重算。
另一种生成方式：我们可以使用优先队列按照n的大小生成候选？类似找最小的n。但较复杂。
由于用户说“因为本题数字不大,所以可以考虑直接暴力枚举所有数字的出现次数”，并给出了两个手动测试的例子，暗示答案也许可以通过简单枚举获得。我可以直接给出最终搜索代码。
也许答案是已知的，我可以计算出来，然后写在代码里输出。但要求是“请给我cpp实现代码”，所以需要写程序逻辑，不仅仅是一个数字。我可以提供能够计算并输出结果的完整代码。
为了确保代码正确，我会包括：
质数生成
DP计算最大层宽度
递归枚举指数（非增）
搜索最小n
输出n
边缘情况：注意n可能很大，需要使用64位整数（long long）。10^4的要求，n可能大约多少？我们可以尝试估计。但long long应该足够（最大9e18）。如果n超过long long，可能需要big integer，但可能性不大？看看5040=2^4*3^2*5*7，最大宽度12。要达到10000，质因子数量和指数会增加。如果n太大，可能溢出。但是已知Project Euler类似问题（Problem 110, 108）等，答案在10^8以内或者更大？这里g(n)是关于除数图的，可能n在10^10左右或更大。我需要使用128位或GMP？在C++标准中可以用__int128，若不行可自己实现大数比较？但在一般比赛中通常long long足够。我们可以估算：比如指数序列15个2，总指数30，n = 2^2 * 3^2 * 5^2 * ... 乘积可能巨大。15个质数前15个质数：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47。全部指数为2的乘积约为 2^2 * 3^2 * ... * 47^2 = (2*3...47)^2。前15个质数乘积约为 6.1e17? 平方后超过64位。所以n可能超过64位。但也许最优解的总指数较小，且集中于前几个质数。为了安全，最好使用支持大整数的库，或者自己写个简单的大数比较（只用于比较和记录最小n）。因为最终只需要输出n，我们可以用数组存n的质因数分解，比较大小时可以用对数或直接比较质因数指数序列（因为都是前几个质数）。对于最小n，给定指数序列，我们可以通过比较对数或比较指数序列的字典序（更大的指数分配给更小的质数）来判断大小。由于指数非增，当我们找到所有符合条件的指数序列后，我们可以为每个序列计算一个“代价”或直接比较大小。因为质数分配是固定的（第i个质数对应指数序列的第i大），所以比较两个指数序列对应的n大小：按顺序从第一个质数开始，指数不同时指数大的n更大？不对，质数小的指数越大，n越大？我们需要比较乘积。可以转换成浮点数log比较，但可能有精度问题。由于我们只需要找到最小的n，可以维护一个最优序列，直接比较对数：sum a_i * log(p_i)。用double可能足够区分，如果很接近可以用精确乘法（使用__int128或手动数组）。考虑到可能需要大数，我可以使用boost多精度或自己写个大整数（仅用于最终比较，记录最优序列的精确值）。另一种方式：使用对数进行排序，最后确定最优候选后，使用Python？但要求C++。可以使用__int128，在GCC中支持。最大指数和可能多大？如果n太大超出128位，可能需要更大。我们可以限制搜索范围。
我们来更精确地分析 g(n) 的增长率。 g(n) = max coef of ∏ (1+x+...+x^{a_i})。
目标是找到最小的 n = ∏ p_i^{a_i} 满足 max coef >= 10000。
这是一个典型的“最小反质数”类似问题。通常可以通过对数剪枝的深度优先搜索：按质数顺序分配指数，保证指数非增。边搜索边计算当前的多项式和当前n的对数，用DP维护当前多项式的系数最大可能值上界，进行剪枝。同时用当前最大值更新全局最优。
我需要写出这样的DFS。我会用double log来评估n的大小，并用__int128或数组记录精确n（仅当找到可行解并需要比较时）。由于10000的门槛不高，我们可以直接用64位整数计算系数（系数最大值可能上万，用int即可）。对于n，用double对数评估大小，当可行解出现时，记录最小的n（通过比较对数，如果对数相近再精确比较）。考虑到搜索空间不大，我们甚至可以枚举所有总指数和 <= 某个上限的序列，用对数找最小。
但更健壮：写一个DFS枚举质因子指数，同时维护多项式系数和n的log值。具体：
预计算前几十个质数和它们的对数。
全局变量：best_log = INF, best_n 序列（或best_n精确值）。
DFS参数：当前质数索引idx（从0开始），当前总指数和？我们不需要总指数和，需要多项式系数。我们可以维护当前多项式系数的数组（动态规划）。
多项式系数DP：开始时多项式为[1]（即常数1）。每添加一个质数，其指数为e，则新多项式为旧多项式卷积上长度为e+1的向量（全1）。我们可以在DFS时携带当前多项式系数向量cur，以及当前最大系数max_coef。当max_coef >= 10000时，计算当前n的log值（sum e_i * log(p_i)），如果小于best_log，更新best_log并记录精确n（可以用字符串或数组表示因数分解，最后算出精确值）。
剪枝：枚举当前质数的指数e，e必须 <= 前一个质数的指数（保证非增）。对于每个e，计算新多项式。同时我们可以估计即使后面指数全为1，最大系数能否达到10000。如果上界小于10000，剪枝。或者可以计算当前最大系数已经>=10000，我们可以继续尝试增加质数（指数为0停止？因为增加质数只会增大n，不会减小n，因为我们用的是递增质数。一旦满足条件，我们不会通过继续增加质数（即增加更多因数）来得到更小的n，因为那样会乘上大于1的数。所以当max_coef >= 10000时，我们记录当前n，然后不需要继续在该分支增加质数（因为后续增加只会让n更大）。但是要注意：有可能当前的指数分配还没包括所有可能的质数，但我们已经达到条件，记录下来后，我们可以回溯，并尝试减少前面质数的指数，可能得到更小的n。所以这是一种剪枝。
因此DFS可以：
参数：质数位置pos（0-based，对应第pos个质数），当前max_e（允许的最大指数，即前一个指数的值），当前多项式coef vector（系数是整数），当前log_n（double）。
初始调用：pos=0, max_e=某个上限（比如100或更大），coef=[1], log_n=0。
在每一层，我们尝试指数 e 从 max_e 降到 0：
如果 e == 0，意味着之后不再添加质数，当前序列结束。检查最大系数是否>=10000，若是则更新最优。
否则，新多项式 coef2 = coef 卷积 [1]* (e+1)（即长度为e+1的全1向量）。
计算 coef2 的最大值 max_c。
新 log_n = log_n + e * log(primes[pos])。
如果当前 log_n 已经大于 best_log，跳过（因为乘的质数>1，之后只会更大）。
如果 max_c 已经 >= 10000，则尝试更新最优（此时不需要继续添加更多质数，因为再添加只会增大n）。但注意：即使max_c >= 10000，我们仍然可以继续尝试e=0（即终止）？我们可以在计算coef2后，如果>=10000，更新最优，然后不继续向更深递归（因为再加深必增大n）。但也要考虑如果e>0，我们也可以选择提前终止（即令后面的指数都是0）。实际上我们在e循环中，当尝试e后，会递归到pos+1，max_e=e。如果在当前层级选择e，然后后面全部选0，就是终止。但我们只需要在递归调用后，当递归返回后继续尝试更小的e。此外，当e=0时意味着终止。所以算法正确。
如果 max_c < 10000，并且存在可能通过增加更多质数达到10000，则继续递归。为了估计上界，可以假设后续所有质数都可以取指数为1（最有利于增加宽度，且最小增加n？实际上宽度上界可以通过假设无限多个指数为1的质数来估计：多项式乘以 (1+x)^k，最大系数是 C(k, k/2)。可以计算若当前max_c与目标差距，需要多少额外的质数，如果即使添加很多质数也无法达到，则剪枝。或者简单设置最大总质数个数，比如最多20个质数。因为指数非增，并且为了达到10000，总质数个数不会太多。
递归后，coef2可以丢弃（或复用）。
优化：
多项式系数用vector<int>。
卷积：对于coef和全1向量卷积，可以原地更新或生成新向量。复杂度：总指数和不超过200，向量长度不超过200，完全可以。
估算上界：当max_c < 10000，我们可以计算如果剩余所有质数均取指数1，我们最多可以乘上 (1+x)^k，其最大系数是中项二项式系数。而二项式系数最大值大约是 2^k / sqrt(pi * k / 2)。对于固定k，这个值可以预计算并用于判断能否达到10000。但因为每次增加质数会乘上(1+x)^{e+1}（实际上是(1+x+...+x^e)），这不是简单的(1+x)。如果要精确估计比较麻烦。不过我们可以不剪枝，只靠max_e最多比如60，总质数最多比如15。枚举空间可能不大。我们尝试评估：指数非增序列，比如第一个指数最大可能多少？如果只有一个质数，max_coef=1 < 10000。两个质数：假设指数 a 和 b，a>=b，最大系数约为 b+1（如果 b <= a）。要达到10000，b≈10000，n≈2^a * 3^b 巨大。所以需要很多质数。类似16个16总和256最大5万。所以最优解可能在总质数15左右，指数较小。指数可能分布为类似[5,5,5,4,4,3,3,2,2,1,1,...]。总质数可能不超过20。指数最大可能不超过20。因此枚举范围很小，我们可以直接暴力枚举所有非增指数序列，不必复杂剪枝。
简单方案：
质数列表：2,3,5,7,11,... (前20个)
枚举所有非增指数序列 a1 >= a2 >= ... >= am > 0，其中m <= 20, a1 <= 某个上限（比如20或30）。我们可以递归生成，并计算多项式和n。
对每个序列，求g(n)，如果>=10000，计算n的log或精确值，记录最小。
最后输出最小n的精确值（用大整数或分解式）。
我需要实现大整数乘法以输出最终的n。可以使用vector<int>存10进制数字，或使用__int128（如果n不超过2^127-1约1.7e38）。我们来估计最优n的范围。类似Project Euler Problem 485? 那个问题是求 sum g(n)。不是。我记起一道题：求最小的n使得g(n) > 1000 之类的。如果g(n)大致相当于将n的质因数指数划分成两半的乘积？其实是多项式的中心系数。已知5040=2^4*3^2*5*7，g=12。总指数=8。中心系数12。要达到10000，总指数大约需要多大？多项式的最大系数在指数分布均匀时最大。如果所有指数都是1，有k个质数，多项式为 (1+x)^k，最大系数C(k, floor(k/2))。C(20,10)=184756 > 10000，C(19,9)=92378 > 10000，C(18,9)=48620 > 10000，C(17,8)=24310 > 10000，C(16,8)=12870 > 10000，C(15,7)=6435 < 10000。所以如果指数全为1，需要至少16个质数，此时n为前16个质数的乘积 = 2*3*5*7*11*13*17*19*23*29*31*37*41*43*47*53 = ? 让我们计算一下这个乘积：这是第16个质数53，乘积大约是 32589158477190044730? 实际上前16个质数乘积大约是 2*3=6, *5=30, *7=210, *11=2310, *13=30030, *17=510510, *19=9699690, *23=223092870, *29=6469693230, *31=200560490130, *37=7420738134810, *41=304250263527210, *43=13082761331670030, *47=614889782588491410, 53=32589158477190044730. 约为 3.25e19，在64位（9e18）之外，但在__int128范围内（max ~1.7e38）。如果指数包含大于1，可能总质数减少，乘积会更大还是更小？例如把一些质数合并：比如将两个指数1的质数变为一个指数2的质数（用较小质数）。比如用2^2 * 3 * 5 * ... 代替 2 * 3 * 5 * ... * p_{16}? 但这样会减少质数个数，需要更多的指数来弥补宽度？实际上为了达到10000，如果减少质数个数，需要增加某些指数。比如分布 [2,1,1,...] 可能乘积比 [1,1,1,...] 小？我们来比较。用具体例子：前16个质数全1，乘积3.25e19。如果我们用15个质数，但其中一个指数为2：序列[2,1,1,...,1] (15个质数)。最大系数？这需要计算多项式系数。可能比全1略大或略小？用16个全1最大系数12870 >= 10000。15个质数中一个指数2其余1，需要总指数16。多项式是 (1+x+x^2)(1+x)^14。最大系数？可以计算，应该小于等于C(16,8) = 12870？不确定。主要我们要最小化n。有时候用较大指数分配给较小质数可以减小乘积。比如用2^2代替2*3（但2*3=6, 2^2=4，更小）。但减少质数可能会降低最大系数，可能需要更多总指数。可能存在一个最优平衡点。无论如何，最小n可能接近甚至小于前16个质数的乘积。可能在64位整数范围内或略超过。我们最好支持大整数（比如用__int128）。我可以在代码中使用unsigned __int128，并在输出时转换为字符串。如果n超出128位，可以自己实现大数乘法，但为简化，我们假设n不超过128位。如果不放心，可以实现简单的大数类，只用于最终输出。
在GCC中，__int128是支持的，但不支持直接cin/cout，需要写输出函数。我可以提供输出函数。
或者使用Python？用户要求cpp，那就cpp with __int128。如果某些编译器不支持，可以用数组实现大数乘法，只用于最终计算最小n。因为我们只需要在找到可行解时用log比较，最后计算出精确值。我们可以将精确值存储为vector<int>（每位0-9）或直接存质因数指数，最终计算乘积。由于候选解不会太多，我们可以在最后通过指数序列来计算大数乘积。用数组手动乘比较保险。
我会这样做：
用long double log值比较大小，记录最优的指数序列（存储在vector<int> best_exp）。
搜索完所有序列后，根据best_exp计算n的大数乘积（使用vector<int>或string），输出。
搜索：
最大指数：我们设定上限MAX_E = 60? 但为保险，动态调整？可以设最大指数为例如60。因为若只有一个质数指数60，g=1。我们需要多个。实际上最大指数可能在10-20之间。枚举时设max_e = 30。
最大质数个数：设MAX_PRIME = 20。
预计算前20个质数。
枚举所有非增指数序列。我们可以用递归函数：search(pos, max_e, current_coef, current_log, current_exp)
其中pos是质数下标，max_e是允许的最大指数（前一个指数），current_coef是当前多项式系数vector<int>，current_log是双精度对数和，current_exp是当前指数序列（用于记录）。
在搜索中，如果我们决定不再添加更多质数（即后面全0），我们直接检查current_coef最大值是否>=10000，若是则比较current_log与best_log，若更小则更新best_log并记录current_exp。
对于e从max_e降到1：
新系数coef2 = conv(current_coef, ones(e+1))
如果coef2最大值>=10000，则这个序列（再加上后面全0）是可行解。我们更新最优（用current_log + e*log(p[pos])），且因为再增加质数只会增大n，所以我们不需要从此分支继续递归（但还要继续尝试更小的e）。
如果coef2最大值<10000，则递归调用pos+1, max_e=e, coef2, current_log + e*log(p[pos]), current_exp加上e。
另外，当e=0时意味着终止，但我们已经在循环外处理终止？
算法改进：我们可以认为在每一层，我们有选项：以e结束（即后面不再有质数），或者继续添加下一个质数。实现时，我们可以在进入函数时，先把当前序列作为候选（如果最大值>=10000）。然后循环e从1到max_e，递归。为了避免重复，可以这样：每次调用search(pos, ...)时，pos是下一个要分配的质数索引。当前已分配的指数保存在current_exp中，current_coef是已分配质数的多项式乘积。我们开始就可以检查current_coef是否满足>=10000。如果满足，则记录。然后继续尝试分配下一个质数（e从1到max_e）。因为即使满足，我们也可以停止，所以记录后不用必须返回，但根据剪枝，一旦满足，再添加质数只会使n变大，因此可以跳过继续递归。所以如果当前已满足，我们就不再循环尝试e>=1，直接返回。这样可以减少搜索。
伪代码：
text
global best_log = INF, best_exp.
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71] // 20个足够
logs = [log(p) for p in primes]
function search(pos, max_e, coeff, current_log, current_exp):
// coeff is polynomial from primes[0..pos-1]
max_c = max(coeff)
if max_c >= 10000:
if current_log < best_log:
best_log = current_log
best_exp = current_exp
return // no need to add more primes as it will increase n
if pos == MAX_PRIME:
return
for e = max_e down to 1:
new_coeff = conv(coeff, e+1) // ones
new_log = current_log + e * logs[pos]
// optional: prune if new_log > best_log
if new_log >= best_log: continue
current_exp.push_back(e)
search(pos+1, e, new_coeff, new_log, current_exp)
current_exp.pop_back()
这里注意：我们在max_c < 10000时才继续添加质数。如果max_c已经>=10000，我们记录并返回，不再加深。
但我们需要考虑一种情况：当前max_c < 10000，但加上e后可能满足，也可能不满足，继续递归。这没问题。
为了计算new_coeff，我们可以复用内存或直接传值。由于系数向量长度最多总和大概200以内，可以每次复制。
现在我们需要实现conv函数：
输入coeff A，整数L（全1的长度，即指数+1）
输出 B，长度为 A.size() + L - 1，B[k] = sum_{i} A[i] * (i <= k <= i+L-1 ? 1 : 0) 这可以通过前缀和或直接双循环。因为都很小，简单双循环即可。注意系数可能超过int范围？最大值10000多，int完全够。
还需要实现max(coeff)。
剪枝：new_log >= best_log 时跳过。因为随着加深log递增，如果当前分支的log已经不小于已知最优log，那么之后只会更大，可以剪掉。但注意double比较可能有精度问题，可以加上微小epsilon或不用太严格。
最后，best_exp将存储最优指数序列（对应前几个质数的指数）。我们需要计算乘积 n = ∏ p_i^{best_exp[i]}。使用大数乘法。我们实现一个简单的字符串或vector乘法。
为了确保正确，我们还需要考虑：指数序列的长度就是质数的个数。序列中可能有0？我们的best_exp只存储了非零指数，因为在递归中只有e>0才push。因此best_exp长度就是使用的质数个数。
最终输出n的十进制表示。
测试：已知g(5040)=12。我们可以用此程序测试 g(5040) 是否输出12？但我们的目标是找>=10000的最小n，不一定能直接验证5040，但可以修改目标为12，看是否能找到5040（或者更小的？）已知g(5040)=12，但最小的n满足g(n)>=12是5040吗？可能是。如果用程序搜索目标12，应能得到5040或类似。我们可以测试一下以确认算法正确。
但是搜索目标10000时，因为枚举空间可能有点大，我们需要评估max_e上限和MAX_PRIME上限。我们不知道最优解的最大指数和质数个数。但我们可以设max_e初始为一个较大的值，比如60，MAX_PRIME=20。由于剪枝和log best，搜索应该很快。因为一旦某个分支log超过best_log就被剪掉。在找到第一个可行解后，best_log会迅速下降，剪掉大部分搜索空间。
我们还可以添加启发式：优先尝试较小的e？或者说由于我们要最小化n，应该先尝试较小的指数？指数小可能log小。但DFS的顺序：我们循环e从max_e down to 1。为了尽快找到较好解，应该先尝试较小的e（因为这样用的质数指数小，可能n较小）。所以我们把循环改为 e = 1 to max_e? 但max_e是由上一个指数决定的，需要保证非增。如果我们从1到max_e，则第一个尝试的e=1（假设max_e允许）。这样可能迅速找到可行解？但这取决于可行性。如果指数太小，可能无法达到10000，我们会一直加深。所以可能先尝试大指数更容易找到可行解？为尽快找到可行解以剪枝，可以从大到小。实际上，第一个可行解可以通过全1序列找到（即指数都是1，直到满足）。全1序列log可能较大。如果我们从大到小，可能会找到指数较大的解，其log可能比全1序列小或大？一般来说，指数分配越均匀，总指数和可能更小，乘积也可能更小。但为了安全，我们可以先运行一次只包含全1序列的检查，得到best_log的上限。然后DFS可以从上界开始剪枝。简单实现：在开始搜索前，手动计算全1序列：从k=1开始，计算C(k, floor(k/2))，直到>=10000，得到k=16。计算其log和n，设为best_log和best_exp。然后再进行DFS。这样DFS有上界剪枝，会更快。
我们可以计算全1序列：k=16，指数序列为16个1。乘积 = 前16个质数乘积。我们在初始化时设定best_log和best_exp为此全1序列。然后DFS中任何log > best_log的都会被剪掉。
另外还需考虑：指数序列不一定全为非零，全1序列长度16。DFS时可以限制最大质数个数到20或稍微大于16，比如25。
现在实现。
细节：
使用double计算log，可能精度足够区分不同乘积，因为乘积是不同质数指数组合。但有可能两个不同序列乘积非常接近，double无法区分导致选错？概率极低，因为质数乘积差异通常很大。如果担心，我们可以保存精确n或指数序列，当log相近时（如差值<1e-9）再用精确大数比较。这里可以简单只依靠double，最后输出时通过best_exp计算精确n即可。
实现大数乘法：vector<int> mul(vector<int> A, int b) 大数乘小整数。最后将best_exp中每个质数的指数次方乘起来。可以先将每个质数p^e计算出来（大数乘小整数循环），然后将这些大数相乘。由于最终n可能很大，我们可以使用vector<int>按10进制存储。
假设我们有函数multiply(string or vector<int>, int) 和 multiply(vector<int>, vector<int>)。直接使用vector<int>，每一位存0-9，顺序从低位到高位。
例：
text
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
vector<int> c(a.size() + b.size(), 0);
for (size_t i = 0; i < a.size(); ++i) {
for (size_t j = 0; j < b.size(); ++j) {
c[i+j] += a[i] * b[j];
c[i+j+1] += c[i+j] / 10;
c[i+j] %= 10;
}
}
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
或乘小整数：
text
vector<int> multiply(const vector<int>& a, int b) {
vector<int> c;
int carry = 0;
for (int x : a) {
int prod = x * b + carry;
c.push_back(prod % 10);
carry = prod / 10;
}
while (carry) {
c.push_back(carry % 10);
carry /= 10;
}
return c;
}
然后求幂：循环乘即可。
最终输出：从高位到低位输出数字。
现在结合所有，编写C++代码。
需要考虑编译环境：使用标准C++11。避免使用不稳定的扩展如__int128。
那么提供完整的代码。
最后，需要包含头文件，主函数等。
我们还需要确认g(n)的计算是否正确。根据题目描述，图的分层，g(n)是任意一层顶点数的最大值。我们推导得出g(n) = max coefficient in ∏ (1 + x + ... + x^{a_i})。题目示例：n=45 = 3^2 * 5^1，指数为2,1。多项式 (1+x+x^2)(1+x) = 1 + 2x + 2x^2 + x^3。最大系数2，g(45)=2。符合。n=5040=2^4*3^2*5*7，指数4,2,1,1。最大系数12。我们可以验证我们的程序对于目标12找到的解是否5040？可以作为可选测试。
现在写最终答案。我会提供代码及简要说明。
|
