「AtCoder JAG2018SC-Day2-C」Equiangular

Description

给定一个正 $n$ 边形，现在要从中选择 $m\ (3 \leq m \leq n)$ 个顶点，把这些顶点相连，得到一个新的多边形，现要求这个多边形的所有内角都相等。求有多少不同形状的多边形满足条件。

$(3 \leq n \leq 10^{12})$

Source

[AtCoder]JAG2018SC-Day2-C

Solution

先考虑正多边形怎么做，对于 $n$ 的所有因数 $x$，我们可以把连续的 $x$ 条线段合成一段，即把 $n$ 条线段分成 $\frac{n}{x}$ 段，这样就能得到一个正 $\frac{n}{x}$ 边形（$\frac{n}{x}$ 至少为 $3$，所以有 $x \leq \frac{n}{3}$）。

举个例子，当 $n = 12$ 时，$x \in \{ 1,2,3,4 \}$ 。

$x=1:$

$x=2:$

$x=3:$

$x=4:$

对于非正多边形，我们可以在正多边形的基础上进行扩展。

正三边形可以扩展为六边形。

正四边形可以扩展为八边形。

其它正多边形以此类推。比较特殊的是，一条线也能进行扩展，可以得到矩形。

很容易得出结论：对于正 $\frac{n}{x}$ 边形（一条线可以看做正二边形，所以这里 $x \leq \frac{n}{2}$），我们对它扩展时，把 $x$ 拆成 $a + b$ 的形式（要满足 $a < b$，不能取 $a = b$，否则还是正多边形，会重复计算），就能得到一个新的 $\frac{2n}{x}$ 边形，一共有 $\frac{x - 1}{2}$ 对 $(a,b)$ 可以取。

很容易得出结论：对于正 $\frac{n}{x}$ 边形（一条线可以看做正二边形，所以这里 $x \leq \frac{n}{2}$），我们对它扩展时，把 $x$ 拆成 $a + b$ 的形式（要满足 $a < b$，不能取 $a = b$，否则还是正多边形，会重复计算），就能得到一个新的 $\frac{2n}{x}$ 边形，一共有 $\frac{x - 1}{2}$ 对 $(a,b)$ 可以取。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

LL n, ans;
vector<LL> v;

int main() {
	read(n);
	for (int i = 1; 1ll * i * i <= n; ++i)
		if (n % i == 0) {
			v.push_back(i);
			if (i != n / i) v.push_back(n / i);
		}
	for (int i = 0; i < (int) v.size(); ++i)
		if (v[i] <= n / 2) {
			ans += (v[i] - 1) / 2;
			if (v[i] <= n / 3) ++ans;
		}
	write(ans);
	putchar('\n');
	return 0; 
}