← 返回题目列表

Codeforces · 1725/G

G. 车库

中文机器翻译题面 查看原题

Pak Chanek 计划建造一个车库。他希望车库由一个正方形和一个直角三角形组成,排列如下图所示。

将 $$$a$$$ 和 $$$b$$$ 定义为直角三角形中两条边的长度,如图所示。整数 $$$x$$$ 是合适的,当且仅当我们可以构造一个车库,并为长度 $$$a$$$ 和 $$$b$$$ ($$$a<b$$$) 分配正整数值,使得底部正方形的面积恰好为 $$$x$$$。作为 Pak Chanek 的好朋友,您被要求帮助他找到第 $$$N$$$ 个最小的合适数字。

输入

唯一一行包含单个整数 $$$N$$$ ($$$1 \leq N \leq 10^9$$$)。

输出

一个整数,表示第 $$$N$$$ 个最小的合适数字。

示例

输入 #1

3

输出 #1

7

注意

$$$3$$$-rd 最小的合适数字是 $$$7$$$。通过指定 $$$a=3$$$ 和 $$$b=4$$$ 可以获得 $$$7$$$ 的正方形面积。