← 返回题目列表

Codeforces · 1242/A

A. 瓷砖画

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

Ujan 最近很懒,但现在决定让他的院子恢复良好状态。首先,他决定粉刷从他家到大门的道路。

路径由 $$$n$$$ 连续的图块组成,编号从 $$$1$$$ 到 $$$n$$$。 Ujan 将为每块瓷砖涂上某种颜色。如果对于任意两个具有数字 $$$i$$$ 和 $$$j$$$ 的不同图块,使得 $$$|j - i|$$$ 是 $$$n$$$ 的除数大于 $$$1$$$,并且它们具有相同的颜色,他将考虑路径美学。正式来说,如果 $$$|i-j| ,则编号为 $$$i$$$ 和 $$$j$$$ 的两个图块的颜色应该相同。 > 1$$$ 和 $$$n \bmod |i-j| = 0$$$ (其中 $$$x \bmod y$$$ 是 $$$x$$$ 除以 $$$y$$$ 时的余数)。

Ujan 想要照亮空间。 Ujan 最多可以使用多少种不同颜色,以使路径美观?

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^{12}$$$),即路径的长度。

输出

输出一个整数,即路径可以绘制的最大可能颜色数。

示例

输入 #1

4

输出 #1

2

输入 #2

5

输出 #2

5

注意

在第一个示例中,两种颜色是最大数量。自 $$$4 \bmod |3-1| 起,图块 $$$1$$$ 和 $$$3$$$ 应该具有相同的颜色= 0$$$。此外,瓷砖 $$$2$$$ 和 $$$4$$$ 应该具有相同的颜色,因为 $$$4 \bmod |4-2| = 0$$$。

在第二个示例中,可以使用所有五种颜色。