题解 CF1096C 【Polygon for the Angle】

## Description $T$ 组数据。给定一个角度 $\theta$，请你寻找一个正 $n$ 边形，满足这个正 $n$ 边形上存在三个顶点 $A,B,C$（可以不相邻），使得 $\angle ABC=\theta$ 。请输出最小的 $n$ 。保证 $n$ 不超过 $998244353$ 。 $(1 \leq T \leq 180,1 \leq \theta < 180)$ ## Solution 正 $n$ 边形是存在外接圆的，且 $n$ 个顶点把圆分成 $n$ 段等长的弧（下文中均称作基本弧），每段基本弧对应的圆心角是 $\left( \frac{360}{n} \right)^\circ$，圆周角是 $\left( \frac{180}{n} \right)^\circ$（圆心角的一半）。  从这个正 $n$ 边形上选 $3$ 个点 $A,B,C$，我们可以看做选择顶点 $B$ 和弧 $\widehat{AC}$ 。弧 $\widehat{AC}$ 对应的圆周角就是 $\angle ABC$（与顶点 $B$ 无关，因为同弧所对的圆周角相等）。弧 $\widehat{AC}$ 的长度一定是基本弧的 $x$ 倍，其中 $x$ 是一个正整数，且不超过 $n - 2$（否则顶点 $B$ 没有位置），所以弧 $\widehat{AC}$ 所对的圆周角就是 $\left( \frac{180x}{n} \right)^\circ$ 。显然我们可以枚举 $n$ 和 $x$，求出正 $n$ 边形可以得到的所有角度。 $n$ 的下界显然是 $3$，$n$ 的上界是什么呢？ 很容易发现当 $n = 360$ 时，$\theta$ 可以等于 $1^\circ \sim 179^\circ$ 中的任意一个角度。所以只要枚举到 $360$ 就好了。注意所给的 $\theta$ 是正整数，所以枚举时要满足 $180x$ 能被 $n$ 整除。 ## Code ```cpp #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); } const int MAXN = 180; int t, n, theta[MAXN + 5]; int main() { for (int i = 3; i <= 360; ++i)//枚举正 n 边形 for (int j = 1; j <= i - 2; ++j)//枚举 x if (180 * j % i == 0 && !theta[180 * j / i])//不能有小数 theta[180 * j / i] = i;//i 就是 θ=(180 * j / i)°时最小的 n for (read(t); t; --t) { read(n); write(theta[n]); putchar('\n'); } return 0; } ```