1096C.md (1477B)
1 Source: https://codeforces.com/problemset/problem/1096/C 2 3 C. Polygon for the Angle 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an angle $\text{ang}$. 22 23 The Jury asks You to find such regular $n$-gon (regular polygon with $n$ vertices) that it has three vertices $a$, $b$ and $c$ (they can be non-consecutive) with $\angle{abc} = \text{ang}$ or report that there is no such $n$-gon. 24 25  26 27 If there are several answers, print the minimal one. It is guarantied that if answer exists then it doesn't exceed $998244353$. 28 29 Input 30 31 The first line contains single integer $T$ ($1 \le T \le 180$) — the number of queries. 32 33 Each of the next $T$ lines contains one integer $\text{ang}$ ($1 \le \text{ang} \lt 180$) — the angle measured in degrees. 34 35 Output 36 37 For each query print single integer $n$ ($3 \le n \le 998244353$) — minimal possible number of vertices in the regular $n$-gon or $-1$ if there is no such $n$. 38 39 Example 40 41 Input 42 43 ``` 44 4 45 54 46 50 47 2 48 178 49 ``` 50 51 Output 52 53 ``` 54 10 55 18 56 90 57 180 58 ``` 59 60 Note 61 62 The answer for the first query is on the picture above. 63 64 The answer for the second query is reached on a regular $18$-gon. For example, $\angle{v_2 v_1 v_6} = 50^{\circ}$. 65 66 The example angle for the third query is $\angle{v_{11} v_{10} v_{12}} = 2^{\circ}$. 67 68 In the fourth query, minimal possible $n$ is $180$ (not $90$).