Polygon of Polygons

正 $N$ 角形から頂点を $k$ 個選び、正 $k$ 角形をつくるには、選んだ頂点が等間隔で並んでいる必要があります。 つまり、 $k$ は $N$ の約数になります。

$k$ を決めたとき、選ぶ頂点を $0$ 個から $\frac{N}{k}-1$ 個ずらすことができるので、選び方は $\frac{N}{k}$ 通りあります。

よって、答えは $\displaystyle\sum_{\substack{k | N \\ k \ge 3}} \frac{N}{k}$ となります。

約数の列挙は $O(\sqrt{N})$ で可能であり、計算量は $O(\sqrt{N})$ となります。