路径

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

路径

时间限制:1s

空间限制:64MB

题目描述

某国有\(n\)个城市,编号分别为\(1,2,..,n\)

编号之差的绝对值小于等于\(21\)的两个城市\(a,b\)之间有交通道路连接,长度为\(lcm(a,b)\),即它们的城市编号的最小公倍数。例如:城市\(6,8\)之间有一条长为\(24\)的交通道路连接,城市\(1,22\)之间有一条长为\(22\)的交通道路连接,而城市\(48,96\)之间没有交通道路连接。

使用交通道路从城市\(1\)到城市\(n\),最短路径是多少?

参考公式: \(lcm(a,b) = a*b / gcd(a,b)\) ,其中\(lcm(a,b)\)表示两个数的最小公倍数, \(gcd(a,b)\) 表示两个数的最大公约数。

输入格式

第一行一个正整数\(n\),表示城市的数量

输出格式

一个正整数,表示最短路径的长度。

样例输入1

23

样例输出1

48

样例1解释

\(1\to 23\)没有直接的路径,但是\(1\to 2\)的路径长度为\(2\), \(2\to 23\)的路径长度是\(46\),共48.

样例输入2

300

样例输出2

22420

数据范围及限制

共\(10\)组测试数据,每个测试点\( 15\)分。

对于\( 40\%\)的数据,\(1< n\le 15\)。

对于\(100\%\)的数据,\(1< n\le 500\)

2021苏青奥赛集训营(2021/7/25训练赛)

未参加
状态
已结束
规则
OI
题目
7
开始于
2021-07-25 08:30
结束于
2021-07-25 11:30
持续时间
3.0 小时
主持人
参赛人数
38