原文 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题面良心地给了翻译。 有乘法，有开方，显然与素因数分解有关。设 n=∏piain=\prod p_i^{a_i}n=∏piai （pip_ipi 为素数，aia_iai 为正整数），那么要使值最小，就要尽量开方。pip_ipi 都是素数，当然没有办法进一步开方。开方的本质是将每一个指数 aia_iai 除以 222，那么令所有 aia_iai 均为 2k2^k2k（kkk 为正整数）时，可以进行 kkk 次开方操作，使 n=∏pin=\prod p_in=∏pi ，值最小。因此第一问的答案即为 n=∏pin=\prod p_in=∏pi 。 第二问中，我们如何令 n=∏(pi)2kn=\prod (p_i)^{2^k}n=∏(pi )2k？显然，将 nnn 乘上 ∏(pi)(2k−ai)\prod (p_i)^{(2^k-a_i)}∏(pi )(2k−ai ) 即可。因此，乘法最多进行一次，因为当乘数为 111 时可以不进行乘法。然后进行 kkk 次开方。那么要让总操作次数最小，就要让 kkk 尽量小。但又注意到 kkk 还需满足 2k−(max⁡ai)≥02^k-(\max a_i) \geq 02k−(maxai )≥0。我们解这个不等式得 k≥log⁡2(max⁡ai)k\geq \log_2 (\max a_i)k≥log2 (maxai )，即最小整数解为 k=⌈log⁡2(max⁡ai)⌉k=\lceil\log_2 (\max a_i)\rceilk=⌈log2 (maxai )⌉。第二问的答案也呼之欲出。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 细节： 1. 要特判 111。上面的讨论都自动排除了 111 这种特殊情况。 2. 仔细思考什么时候不用进行乘法操作。