主題
題目連結(jié)：
題目大意：
輸入第一列給定一正整數(shù) T（1 ≦ T ≦ 10），代表測(cè)試資料筆數(shù)，每筆佔(zhàn)一列。每列給定兩正整數(shù) N 、 K（2 ≦ N ≦ 10 ^ 4、3 ≦ K ≦ 100），代表現(xiàn)在你有 N 個(gè)大小相等的正三角形，試問你是否可以藉由這 N 個(gè)正三角形拼湊出一個(gè)凸 K 邊形（三角形必須全部使用）。
其中正三角形的拼湊有以下兩條限制：
一，每個(gè)三角形至少要有一邊與其他三角形相接（N = 1，視為規(guī)則成立。即所有三角形應(yīng)聚在一塊，而沒有獨(dú)立自己一區(qū)者）
二，兩個(gè)三角形之間的相接需為一邊「完整地」與另一邊重合。
如上圖中的左側(cè)即符合規(guī)則一、二；而右側(cè)則不符合規(guī)則二（且該圖形非凸多邊形）。
範(fàn)例輸入：
5
2 3
2 4
4 5
6 6
7 7
範(fàn)例輸出：
no
yes
no
yes
no
解題思維：
由於我們的目標(biāo)是凸多邊形，因此其內(nèi)角應(yīng)皆小於 180 度。可以看到一個(gè)正三角形是 60 度、兩個(gè)正三角形拼在一起為 120 度，所以我們可以形成 60 度以及 120 度這兩種內(nèi)角角度。然而這就是極限了，因?yàn)樵俣嗑蛣偤?180 度了，因此三個(gè)以上（含）正三角形形成一個(gè)內(nèi)角是不可能的事情。
那麼根據(jù)上面的條件，我們實(shí)際上有機(jī)會(huì)可以湊出哪些多邊形呢？答案是 3 ≦ K ≦ 6 的這些傢伙們（3 ≦ K 這個(gè)條件很自然，畢竟至少三條邊才能圍成一個(gè)封閉圖形）。原因很簡(jiǎn)單：
由於任意一個(gè)凸多邊形的外角總和為 360 度（簡(jiǎn)單證明：讀者可以隨便拿個(gè)凸多邊形從任意一頂點(diǎn)開始繞一圈回到原點(diǎn)，過程中每次轉(zhuǎn)彎之角度即為一外角。而繞一圈後即回到原點(diǎn)並「面朝同方向」，因此外角總和為 360 度），因此如果存在外角太小則會(huì)使某個(gè)內(nèi)角過大。而可以看到我們最大的內(nèi)角為 120 度，因此外角最小只能是 60 度，不能再小。
因此可以看到
360 ÷ 3 = 120
360 ÷ 4 = 90
360 ÷ 5 = 72
360 ÷ 6 = 60
360 ÷ 7 < 60
……
因此當(dāng) K = 7 以上（含）時(shí)，其外角將必有一者是小於 60 度的。因此我們不可能湊出 K = 7 以上（含）的凸 K 邊形。
那在哪些條件下我們可以湊出 K = 3 、 4 、 5 、 6 呢？
（以下假設(shè)我們使用的三角形之邊長(zhǎng)為 1，而這等等會(huì)派上用場(chǎng)）
首先是簡(jiǎn)單的 K = 3 和 4：
當(dāng) K = 3 時(shí)，可以看到這個(gè) 3 邊形必須為正三角形（因?yàn)閮?nèi)角都是 60 度）。因此設(shè)其邊長(zhǎng)為 s（因?yàn)橐粋€(gè)單位正三角形的邊長(zhǎng)為 1，因此 s 為正整數(shù)）。而正三角形面積之公式為
(邊長(zhǎng) ^ 2) × (√3) ÷ 4
因此比較一下這個(gè)組出來的大正三角形與組成單位之小正三小形之面積，可以得到我們需要 s ^ 2 個(gè)小的正三角形來組出大的。
也就是說當(dāng) N = 1 ^ 2 、 2 ^ 2 、 3 ^ 2 、 4 ^ 2 、……，即 N 為完全平方數(shù)時(shí)，我們可以造出一個(gè) 3 邊形。
接著是當(dāng) K = 4 時(shí)，可以看到 N = 1 是一個(gè)正三角形不是 4 邊形。但是除此之外的 N 值，我們可以按照下圖的方式
來形成 4 邊形。因此對(duì)於 N ≧ 2，我們都有辦法可以組成一個(gè) 4 邊形。
接著是 K = 5：
從內(nèi)角的觀點(diǎn)出發(fā)，我們唯一可能的拼法是令其中一個(gè)內(nèi)角為 60 度，其他四個(gè)則為 120 度，且 5 邊形的邊長(zhǎng)為整數(shù)（因?yàn)閱挝徽切蔚倪呴L(zhǎng)為 1）。因此我們可以畫出下圖的 5 邊形（如塗成灰色之區(qū)域所示）
其中 60 度的角之兩腰與那個(gè)角的對(duì)邊，這三條邊往兩側(cè)延長(zhǎng)可以形成邊長(zhǎng)為 q 與邊長(zhǎng) r 的兩個(gè)正三角形（如上圖所示）。因此我們可以將這整個(gè) 5 邊形看成是一個(gè)較大的、邊長(zhǎng)為 p 的正三角形，經(jīng)由紅色的兩條直線切割掉邊長(zhǎng) q 以及邊長(zhǎng) r 的正三角形所留下的「面積」。
因此回到 K = 3 時(shí)的論點(diǎn)，邊長(zhǎng) x 代表其需要 x ^ 2 小正三角形所組成。因此我們可以看到這個(gè) 5 邊形實(shí)際上是由 p ^ 2 - q ^ 2 - r ^ 2 個(gè)小正三角形所組成。其中，可以看到 p 、 q 、 r 皆為正且因?yàn)?60 度的角之對(duì)邊的邊長(zhǎng)應(yīng)為正數(shù)，因此大的正三角形之邊長(zhǎng) p 應(yīng)大於 q + r。
總結(jié)：當(dāng) X = p ^ 2 - q ^ 2 - r ^ 2 時(shí)（其中 p 、 q 、 r ≧ 1 且 p > q + r），我們可以用 X 個(gè)正三角形組出一個(gè) 5 邊形（只要按照上圖的方式排列即可）。
最後是 K = 6，而這其實(shí)跟 K = 5 的情況很像，如下圖
因此可以推得當(dāng) X = p ^ 2 - q ^ 2 - r ^ 2 - s ^ 2 時(shí)（其中 p 、 q 、 r 、 s ≧ 1 且 p > q + r 且 p > q + s 且 p > r + s），我們便可以使用 X 個(gè)正三角形組出一個(gè) 6 邊形。
接著的問題是，我們要怎麼判斷 N 個(gè)正三角形可以形成一個(gè) K 邊形？K = 3 、 4 的情況比較簡(jiǎn)單，不管是建表還是直接判斷都相當(dāng)直接；而 K = 5 、 6，如果我們要直接判斷的話需要分解 N 這個(gè)數(shù)字（例如說 K = 5，則我們需要找到數(shù)組 (p, q, r) 滿足 p ^ 2 - q ^ 2 - r ^ 2 = N）。
但是對(duì)於 K = 5 、 6，說實(shí)話我沒有好的分解法或是窮舉法QQ。我在下方附的範(fàn)例程式的應(yīng)該是假解，窮舉 p 的範(fàn)圍似乎沒有完全覆蓋到該有的。不過我也無法說明，希望有大大可以指點(diǎn)迷津。
本題實(shí)際上有一篇相關(guān)的論文存在，即
Eike Hertel, Christian Richter: Tiling Convex Polygons with Congruent Equilateral Triangles (2014)
裡面就是在討論本題之題目。而且還證明了 T5 的補(bǔ)集（T5 即為「可以湊出五邊形的正三角形個(gè)數(shù)」形成之集合，其補(bǔ)集即為除此之外的正整數(shù)）為歐拉（Leonhard Euler）提出之 Idoneal Number 這個(gè)有限數(shù)列的一個(gè)子集。而因?yàn)?Idoneal Number 本身的性質(zhì)之緣故，因此與廣義黎曼猜想（Generalized Riemann Hypothesis）產(chǎn)生了連結(jié)。
而 T5 和 T6 的補(bǔ)集都是有限集合，因此其實(shí)也可以直接偷吃步窮舉補(bǔ)集的判斷即可。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
達(dá)人
