给定一根长度为 n 的绳子(n 为正整数),要求将这根绳子剪成至少两段,每段长度均为正整数。请你设计一种方法,使得所有可能的切割方案中,各段长度的乘积达到最大值,并输出这个最大乘积。
当 n = 8 时,有以下几种可能的切割方式及对应乘积:
1 + 7,乘积为 1 × 7 = 7
2 + 6,乘积为 2 × 6 = 12
3 + 5,乘积为 3 × 5 = 15
2 + 3 + 3,乘积为 2 × 3 × 3 = 18
因此,该例中最大乘积为 18。
输入一个正整数 n,代表绳子的总长度。
输出一个整数,表示将绳子剪成若干段后,各段长度乘积的最大值,如果无解则输出 Impossible
。
由于最终答案可能非常大,只需要输出最终结果取模 2092999 的结果即可。
8
18
对于 30% 的测试数据, 满足 1 ≤ n ≤ 10;
对于 60% 的测试数据, 满足 1 ≤ n ≤ 100;
对于 90% 的测试数据, 满足 1 ≤ n ≤ 10^8;
对于 100% 的测试数据, 满足 1 ≤ n ≤ 10^15;