Description
给定一个角度 ( heta)，请你寻找一个正 (n) 边型，满足在这个正 (n) 边型上找三个顶点 (A,B,C) （可以不相邻），使得 (angle ABC~=~ heta) 。请输出最小的 (n)。保证 (n) 不超过 (998244353)。多组数据。
注意给出的 ( heta) 是使用角度制表示的。
Input
第一行是数据组数 (T)
下面 (T) 行，每行一个整数 ( heta)，代表给出的角度
Output
对于每组数据输出一行代表答案
Hint
(1~leq~T~leq~180~,~1~leq~ heta~<~180)。
Solution
多边形内角和定理：
对于一个有 (n) 个顶点的凸多边形 (n~geq~3)，其内角和为 ((n~-~2)~ imes~180^circ)。
证明略。这大概是初中定理吧……大概方法是显然一个 (n) 边型可以分成 ((n~-~2)) 个三角形，每个三角形的内角和是 (180^circ)。至于证明可以分成 ((n~-~2)) 个三角形，对 (n) 做数学归纳即可。
由于这是一个正 (n) 边型，所以一个角的度数为 (frac{n-2}{n}~ imes~180^circ)
同时它连向其他每个顶点的线段平分这个角，所以它连向相邻两个顶点的线段组成的角的度数为 (frac{n-2}{(n-2)n}~ imes~180^circ~=~frac{1}{n}~ imes~180^circ)
我们设选择的点 (A) 和点 (C) 中间相隔了 ((k-1)) 个顶点 ((k~leq~n~-~2))，于是这些一共组成了 (k) 个角度如上的角。列得方程如下（角度略去）：
移项得
我们设 (s~=~gcd( heta~,~180))，然后等式两侧同除 (s)，得
(frac{180}{s}~ imes~k~=~frac{ heta}{s}~ imes~n)
由于(frac{180}{s}~perp~frac{ heta}{s})，所以 (k~=~frac{ heta}{s}~,~n~=~frac{180}{s})
考虑这种情况下我们要求 (k~leq~n~-~2)，但是如果算出来不是这样怎么办：如果答案为 (n) 时满足上式，则答案为 (xn(x~in~Z^+)) 时一定也满足上式。于是我们不断加 (n) 直到合法即可。
Code
#include <cstdio>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endif
#define rg register
#define ci const int
#define cl const long long
typedef long long int ll;
namespace IPT {
const int L = 1000000;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) {
end = buf + fread(front = buf, 1, L, stdin);
if (front == end) return -1;
}
return *(front++);
}
}
template <typename T>
inline void qr(T &x) {
rg char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
if (lst == '-') x = -x;
}
template <typename T>
inline void ReadDb(T &x) {
rg char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar();
if (ch == '.') {
ch = IPT::GetChar();
double base = 1;
while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar();
}
if (lst == '-') x = -x;
}
namespace OPT {
char buf[120];
}
template <typename T>
inline void qw(T x, const char aft, const bool pt) {
if (x < 0) {x = -x, putchar('-');}
rg int top=0;
do {OPT::buf[++top] = x % 10 + '0';} while (x /= 10);
while (top) putchar(OPT::buf[top--]);
if (pt) putchar(aft);
}
const int maxn = 200010;
const int MOD = 998244353;
int n;
ll ans;
char MU[maxn];
int main() {
freopen("1.in", "r", stdin);
qr(n);
for (rg int i = 1; i <= n; ++i) do {MU[i] = IPT::GetChar();} while ((MU[i] > 'z') || (MU[i] < 'a'));
MU[0] = MU[1]; MU[n + 1] = MU[n];;
int pos = n; while (MU[pos] == MU[0]) --pos;
int k = n - pos;
for (rg int i = 1; i <= n; ++i) if (MU[i] == MU[i - 1]) {
++ans;
} else break;
ans = (ans * k) % MOD;
++ans;
for (rg int i = 1; i <= n; ++i) if (MU[i] == MU[i - 1]) ++ans; else break;
for (rg int i = n; i; --i) if (MU[i] == MU[i + 1]) ++ans; else break;
qw(ans % MOD, '
', true);
return 0;
}