## ZJ i253 - 正三角形非常好......差不多一樣凸多邊形 題解

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 針對不同的 $K$ 做討論

雖然本題 $K \leq 100$，但其實我們可以先討論一些 $\text{case}$ ，如果 $K \geq 7$ 時，因為用正三角形的緣故，角度只能組合出 $60°$ 或 $120°$ ，而如果 $K = 7$，已知七邊形的內角和為 $900°$，而 $900/7 = 128.57 > 120$，所以發現 $K \geq 7$ 時一定組不出來 (不論 $N$ 如何，更大的 $K$ 算出來平均只會更大)，所以接著我們只要討論 $3 \leq K \leq 6$ 的情況即可。

### $K = 3$

三角(邊)形的內角和為 $180°$，只有一種拆法 : $60+60+60$，也就是是正三角形的時候，所以其實如果 $N$ 是完全平方數的時候就可以構造出來，否則就不行，這個檢查可以用 $O(\sqrt{N})$ 或 $O(logN)$ 的複雜度求得 (根據實作方法) 。

### $K = 4$


以上是一個構造方法，發現只要 $N \geq 2$ 都有解 (梯形) 。

### $K = 6$

我們先不討論 $K=5$ ，因為其實他和 $K = 6$ 很相似。


其實每個六邊形都可以分成像這樣，三個部分，會發現綠色部分是類似平行四邊形這樣，然後藍色跟紅色的的部分是等腰梯形，我們如果像上圖一條一條線算他們的三角形數，會變成下面這樣(假設綠色的一條是 $x$) :

綠色 : $x+x+x+...+x$
紅色 : $(x-1)+(x-3)+(x-5)+...+y$
藍色 : $(x-1)+(x-3)+(x-5)+...+z$

我們可以窮舉 $x, y, z$ ，然後先算出紅色及藍色的面積，然後綠色的面積其實就會是 $N$ - 紅色 - 藍色，然後檢查這東西能否整除 $x$ 就好了。

那 $x, y, z$ 的上界要到多少呢，一般來說應該要是到 $N$，但是其實一個六邊形可以想像成一個大的正三角形截去三個角，所以其實弄到 $\sqrt{N}$ 就行了，因此檢查一個的時間複雜度是 $O(N^{1.5})$。
### $K = 5$

同上面的解法，把 $x,z$ 其中一個固定成 $1$ 就是 $K=5$ 的解法了。

### 結論

我們可以發現不管哪一種 $\text{case}$ 最多一筆測資需要 $O(N^{1.5})$ 的時間判斷，$T$ 筆就是 $O(T \cdot N^{1.5})$，已經足夠快通過。 (感謝 Ststone 提供解題方向) 另外，如果改變一下實作方法，其實也可以做到 $O(N^{1.5}+T)$，不過這題 $T \leq 10$，所以本來的方法其實就夠快了。

後面是一些偷吃步 : $K = 5, 6$ 的情況，其實有試著在本機建表過 (跑完所有小於 $10000$ 的 $N$ )，但其實最後一組不能構造出來的 $N$ 遠小於題目的範圍限制 (這點我還不知道怎麼證明)，所以其實本機建表也不是行不通，然後感謝 inversion 這篇 [blog](https://home.gamer.com.tw/artwork.php?sn=5474302) 其實有提到相關的方法，他也有說有一篇論文就是在證明 $K=5, 6$ 的補集是有限集合，有興趣的可以參考看看。