「Codeforces 1096C」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)$

Source

[Luogu]CF1096C

[Codeforces]1096C

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

#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;
}