正 NNN 角形から頂点を kkk 個選び、正 kkk 角形をつくるには、選んだ頂点が等間隔で並んでいる必要があります。 つまり、 kkk は NNN の約数になります。
kkk を決めたとき、選ぶ頂点を 000 個から Nk−1\frac{N}{k}-1kN−1 個ずらすことができるので、選び方は Nk\frac{N}{k}kN 通りあります。
よって、答えは ∑k∣Nk≥3Nk\displaystyle\sum_{\substack{k | N \\ k \ge 3}} \frac{N}{k}k∣Nk≥3∑kN となります。
約数の列挙は O(N)O(\sqrt{N})O(N) で可能であり、計算量は O(N)O(\sqrt{N})O(N) となります。