[Codeforces] Educational Codeforces Round 59 C. Polygon for the Angle

Polygon for the Angle

https://codeforces.com/contest/1096/problem/C

考え方

題意

正 \( n \) 角形の頂点を3つ選んでできる角度を \( \theta \) とします。\( \theta \ (1 \leq \theta \leq 179)\) が与えられたとき、\( n \) の最小値を答えます。

方針

正 \( n \) 角形の内角は、\(\dfrac{180(n – 2)}{n}\) となります。また、頂点を3つ選んでできる角度は、\(\dfrac{180(n – 2)}{n} \dfrac{k}{n – 2} = \dfrac{180k}{n} \ (1 \leq k \leq n – 2)\) となります。これは、正 \( n \) 角形の内角は頂点を3個選んだ時、 \( k \) 個分割することができるからです。

\( \dfrac{180k}{n} = \theta \) とすると、

\[ n = \dfrac{180k}{\theta}\]

となります。\( k = \theta\) とすると、\( n = 180 \) となります。

ここで、\( \theta = 179 \) のときを考えると、\( n = 180 \) は \( k \leq 178\) なので、\( k = 2 \times 179 \) として、\( n = 360 \) となります。

\(p, q\) を互いに素な自然数として、\( \dfrac{180}{\theta} = \dfrac{p}{q}\) とすると、\( p – q \leq 2\) ならば、\(n = p\) そうでなければ、\( n = 2p\) とすることができます。

コード

感想

考察が難しいと思いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする