P1369 - 变 - 优加优智OJ系统

内存限制：2 MB 时间限制：1.000 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：3 通过：1

对于 2 以上（包括 2），n 以下（包括 n）的正整数 x 可以进行以下操作。
如果 x + 1 ≤ n，x + 1 可变为新的 x
如果 sqrt( x )为整数， sqrt( x ) 可变为新的 x
例如：x = 2 时，新的 x 可以为 3。x = 4 时，新的 x 可以为(2, 5)中的任意一个。

kagamiz想知道从 x = 2开始，将所有允许的操作都执行至少一遍，使 x 的值再次为 2 的方法中，操作次数最少的方法的操作次数。

你的任务就是判断这样的方法是否存在，如果存在，则输出最小操作次数。

输入 1 行， 1个整数 n。

    输出 1 行最小操作次数。当不存在符合条件的方法时输出 -1。
举例，比如所有允许的操作共有9个，请看如下提示：
2 -- > 3
3 -- > 4
4 -- > 5
5 -- > 6
    6 -- > 7
7 -- > 8
8 -- > 9
4 -- > 2
9 -- > 3
    将以上操作都至少执行一遍，以x = 2时的最小操作次数为 10，操作过程依次如下：
2 -- > 3
3 -- > 4
4 -- > 5
5 -- > 6
6 -- > 7
7 -- > 8
8 -- > 9
9 -- > 3
3 -- > 4
4 -- > 2

50% 的数据：2 ≤ n ≤ 3 × 10³；
100% 的数据：2 ≤ n ≤ 10¹²(任意时刻都不能超过的上限值)。

动态规划

提交提交记录统计

1369: 变

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签