240911 - 绳子剪切

题目描述

给定一根长度为 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;

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 117
通过人数 33
金币数量 3 枚
难度 提高


上一题 下一题