路径
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
路径
时间限制: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