← 返回题目列表

AtCoder · jag2018summer_day2_c

C. 等角

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

分数: 100 点

问题陈述

你有一个常规的 N边凸多边形。 你将要选择 3 或来自多边形的更多顶点,并创建一个新的凸多边形 P 由选定的顶点形成。 你非常喜欢等角多边形(顶角全部相等的多边形),所以多边形 P 必须是等角的。

计算通过上述方法可以得到的等角多边形的数量。 这里,如果两个多边形全等,即一个多边形具有与另一个多边形相同的形状和大小或者是另一个多边形的镜像,则认为它们是相同的。

约束

  • 3 \leq N \leq 10^{12}

输入

输入由标准输入按以下格式给出:

N

输出

打印您可以获得的等角多边形的数量。


示例输入 1

6

示例输出 1

3

您可以获得以下信息 3 多边形。


示例输入 2

10

示例输出 2

4

您可以获得以下信息 4 多边形。


示例输入 3

1000000000000

示例输出 3

749847411091