題目連結(jié)：
題目大意：
輸入有多筆測試資料，每筆佔一列。每列給定兩正整數(shù) n 、 k（3 ≦ n ≦ 500，1 ≦ k < n），代表現(xiàn)在有 n 位 Loki 各自佔據(jù)正 n 邊形的一個頂點。
該正 n 邊形的邊長為 1 公尺長，且頂點被順時針編號為 0 ～ n - 1。而編號 i 的 Loki 會去追編號 i + k 的 Loki（當(dāng) i + k ≧ n 時，為 i + k - n，即 i + k 模 n 之值）。已知所有 Loki 的速度固定為每秒 1 公尺。
試問多少秒後所有 Loki 會聚集在正 n 邊形的正中心？請將秒數(shù)四捨五入至小數(shù)點第二位後輸出。
範(fàn)例輸入：
3 1
3 2
4 1
4 2
4 3
5 1
6 1
7 1
8 1
10 1
20 1
50 1
100 1
200 1
87 86
94 87
89 4
8 7
範(fàn)例輸出：
0.67
0.67
1.00
0.71
1.00
1.45
2.00
2.66
3.41
5.24
20.43
126.82
506.77
2026.59
383.62
64.55
100.68
3.41
解題思維：
（文極長、大量數(shù)學(xué)式子、圖多注意。文末有「結(jié)論」）
（如果死圖，請先重整。若多次重整或點進(jìn)圖片都無法解決請通知我）
首先，我們需要將所有 Loki 的位置座標(biāo)化。
我們可以隨便選擇一個位置定為原點 (0, 0) 然後讓正 n 邊形的一條邊放在 +X 方向上，剩下的部分則往 +Y 方向延伸?？梢詮南聢D n = 8 的例子
中看到各個點的座標(biāo)從原點按照逆時針方向依序為
(0, 0)、
(1, 0) 同時也是 (cos 0, sin 0)、
(cos 0 + cos θ, sin 0 + sin θ)、
(cos 0 + cos θ + cos 2θ, sin 0 + sin θ + sin 2θ)、
……
也就是每個點為前一個點的座標(biāo)值加上一個偏移量。而該偏移量原本為 (1, 0)，每轉(zhuǎn)一個彎後就會旋轉(zhuǎn) θ 弧度。因此如果轉(zhuǎn)了 q 個彎，偏移量將是 (cos qθ, sin qθ)，而其長度維持為 1 單位長。
其中 θ 為正 n 邊形的外角。因為外角總和為 360°（即 2π 弧度），因為如果你從邊上任一個位置出發(fā)繞一圈回來，你會發(fā)現(xiàn)你恰好「轉(zhuǎn)了」2π 弧度。因此 θ = 2π ÷ n（因為要轉(zhuǎn) n 次彎）。
因此可以看到一個點如果需要從原點按逆時針走 m 條邊才能到，則該點座標(biāo) (x, y) 為
x = cos 0 + cos θ + cos 2θ + …… cos (m-1)θ
y = sin 0 + sin θ + sin 2θ + …… sin (m-1)θ
而原點本身會被定義為繞一圈回來後的點，即 m = n。
我們在此定義以上座標(biāo)系為 P1。
此時我們將這些點重新編號：原點為編號 0，逆時針依序為編號 1 、 2 、…… 、 n - 1。而我們可以想像：當(dāng)所有 Loki 位於正 n 邊形的中心時，即代表著編號 0 第一次追上了編號 k 的 Loki。
因此我們只要知道編號 0 與編號 k 的 Loki 的相對速度以及一開始的距離，然後將距離除以速度即可得到追上的時間，也就是到達(dá)中心的所需時間。而其他對的條件與編號 0 與編號 k 這對相同，所以可以只考慮這對。
而為了知道編號 0 與編號 k 的 Loki 的相對速度，我們同時也需要編號 2k 的 Loki，因此我們需要算出編號 k 和編號 2k 的位置。雖然可以按照上面的式子慢慢地一個點一個點地推得。
而我們也可以利用公式求得點座標(biāo)，而公式可以參考這題的作法推得。不過，公式還可以從別的角度推得——我們一樣利用一個正 n 邊形，只是這次原點位於圖形的中心。因此所有點的座標(biāo)如下圖所示：
其中 r 為頂點到正 n 邊形中心的距離，同時也是正 n 邊形的外接圓半徑?？梢钥吹酵饨訄A同時也是三角形 ABC 的外接圓，因此根據(jù)正弦定理（Law of Sines）可得
r = s ÷ (2sin(θ ÷ 2))
其中 s 為正 n 邊形的邊長，在本例中為 s = 1。並且我們將此座標(biāo)系稱為 P2。
可以看到原先座標(biāo)系 P1 的原點對應(yīng)到本座標(biāo)系 P2 的點 C、編號 1 對應(yīng)到點 A 、……以此類推。因此可以看到上圖中的紅色線即為原座標(biāo)系 P1 位於 X 軸上的那條邊。
而我們可以得出該條邊與 X 軸的夾角為 T = (π - θ) ÷ 2 弧度。所以將整個座標(biāo)順時針旋轉(zhuǎn) T 弧度，紅色邊將與 X 軸平行。
因此 P2 座標(biāo)系原本的每個點
(rcos(Mθ), rsin(Mθ))
現(xiàn)在變?yōu)?/div>
(rcos(Mθ - T), rsin(Mθ - T))
得新座標(biāo)系 P2'
可以看到原本座標(biāo)系 P1 的原點現(xiàn)在位於 P2' 座標(biāo)系的
(-rsin(θ ÷ 2), -rcos(θ ÷ 2))
因此將整個座標(biāo)系平移 (rsin(θ ÷ 2), rcos(θ ÷ 2)) 就變回原本的座標(biāo)系 P1 了。不過此時可以看到 P2' 的點變?yōu)?/div>
(rcos(Mθ - T) + rsin(θ ÷ 2), rsin(Mθ - T) + rcos(θ ÷ 2))
而 P2' 座標(biāo)系的 M 之值對應(yīng)著 P1 座標(biāo)系的 m - 1。所以我們便證明了
cos 0 + cos θ + cos 2θ + …… cos (m-1)θ
等價於
rcos((m - 1)θ - T) + rsin(θ ÷ 2)
且
sin 0 + sin θ + sin 2θ + …… sin (m-1)θ
等價於
rsin((m - 1)θ - T) + rcos(θ ÷ 2)
因此將 r 、 T 展開後可得 x 座標(biāo)為
而 y 座標(biāo)為
回到題目本身，我們需要編號 k 和編號 2k 兩個 Loki 的位置，而它們的座標(biāo)套用 m = k 和 m = 2k 即可求得。
我們定義編號 k 位於 (xk, yk) 、編號 2k 位於 (x2k, y2k)。
因為編號 0 要追著編號 k，而編號 k 要追著編號 2k。所以兩者各自有著方向向量 d1 = (xk, yk) 和 d2 = (x2k - xk, y2k - yk)。不過如果我們現(xiàn)在放任他們跑剛好一秒（這邊只沿著向量走，沒有跟著 Loki 們的位置變動而變動方向），他們移動到的位置並不是原座標(biāo)直接加上這兩個向量，因為這兩個向量的長度不一定為 1。
因此我們需要將算出 L1 = sqrt(xk ^ 2 + yk ^ 2) 、 L2 = sqrt((x2k - xk) ^ 2 + (y2k - yk) ^ 2)，其中 sqrt() 為取平方根。
然後將 d1 除以 L1 、d2 除以 L2 便可以將兩個向量長度調(diào)整為 1。令這兩個向量為
d1' = (dxk, dyk)
d2' = (dx2k, dy2k)
因此現(xiàn)在如果我們放任他們移動 dt 秒（在不做方向更新的情況下），編號 0 、編號 k 的位置將位於
(dxk × dt, dyk × dt)
和
(xk + dx2k × dt, yk + dy2k × dt)
因此 dt 秒後編號 0 與編號 k 的座標(biāo)差距為
(xk + (dx2k - dxk) × dt, yk + (dy2k - dyk) × dt)
將其命名為
(dx, dy)
因此 dt 秒後它們兩個的距離從 L1 變成了
sqrt(dx ^ 2 + dy ^ 2)
令此值為 d。因此兩者的相對位移為
L1 - sqrt(dx ^ 2 + dy ^ 2)
根據(jù)「距離除以時間等於速率」，因此兩者的相對速率為
(L1 - sqrt(dx ^ 2 + dy ^ 2)) ÷ dt
而我們可以看到在任何時刻下，編號 0 與編號 k 的相對速率 v 應(yīng)維持一定值。因為整個系統(tǒng)是對稱的（每對 Loki 都經(jīng)歷著相似的移動路徑），所以不管何時（直到抵達(dá)中心為止）這些 Loki 都可以形成一個稍微旋轉(zhuǎn)後縮小版本的正 n 邊形，如下圖 n = 5 、 k = 1 時的示意圖：
（值得注意的是，這只是一個逼近示意圖，與真實情況有所差別）
所以當(dāng)我們將 dt 盡可能地逼近 0 時，上面的相對速率之值便會收斂於實際的相對速率 v，也就是 v =
但是當(dāng)我們直接代入 dt = 0 時，會發(fā)現(xiàn)分子分母都會是 0，代表其為「0/0」之不定式（Indeterminate Form）。因此可以套用羅必達(dá)法則（L'H?pital's Rule，參見維基）將分子分母各自對 dt 微分，求得
然後將 dx 、 dy 的定義值代入進(jìn)去便可以得到相當(dāng)長的式子（暫時如此），其為
這時可以將上式代入 dt = 0 了，得
可以看到分子為 d1 向量與 (d1' - d2') 這個向量之內(nèi)積（Dot Product），因此先改寫為
套入內(nèi)積
其中 d1 的長度恰好就是 L1 且 d1' = d1 ÷ L1 、 d2' = d2 ÷ L2，再加上 L2 實際上等於 L1。因為編號 0 到編號 k 的距離理所當(dāng)然地應(yīng)等於編號 k 到編號 2k 的距離。因此可以改寫為
那麼 cosA 呢？其按內(nèi)積定義為 d1 與 (d1' - d2') 之夾角。而該角度同時也是 d1 、 (-d2) 、 (d1 - d2) 三個向量所形成的三角形中與 d2 相對之角度，如下圖 n = 6 、 k = 2 時的示意圖：
是故，根據(jù)餘弦定理（Law of Cosines）可以求出
其中 L 為 (d1 - d2) 這個向量的長度。因此式子便成為了
接著我們要求 L ^ 2 的值，可以看到其值為
將等號右邊展開為
合併一些項次（令 L2k 為原點到 (x2k, y2k) 的距離）且再套用一次內(nèi)積便改寫為
而角度 α 為 (xk, yk) 、 (x2k, y2k) 以及 d2 這三個向量圍成的三角形中與 d2 相對之角度，且別忘記 d2 的角度恰為 L1。因此再度根據(jù)餘弦定理可得
因此 L ^ 2 等價於
也因此我們費盡千辛萬苦終於求得了相對速率 v 的值為
最後，因為編號 0 的 Loki 與編號 k 的 Loki 距離 L1。而我們也已經(jīng)知道相對速率 v，所以可以推得所有 Loki 位於正 n 邊形的中心所需時間恰為 L1 ÷ v ，即
結(jié)論：
編號 k 與編號 2k 的 Loki 相對於編號 0 之座標(biāo)可以表為
作為其 X 、 Y 座標(biāo)（代入 m = k 以及 m = 2k 即可）。
而我們將編號 0 與編號 k 的距離定為 L1 、編號 0 與編號 2k 的距離定為 L2k，則抵達(dá)中心所需時間為
（2021 / 7 / 27 14:52 更新：作者有在留言區(qū)用一句話講解他使用的公式，只用了一句話和一張圖XD）
題外話：
如果有人想到了更精簡的證明過程（等價的公式也行），我強(qiáng)烈地希望可以告訴我。當(dāng)然如果上述內(nèi)容有紕漏，哪怕是多小的錯誤都?xì)g迎指正。
本題我花了半天到一天想出解法（實際上是邊調(diào)整、邊天馬行空想出來的，總共提交了 27 次的程式碼），而統(tǒng)整成以上的過程則花了整整兩天。很久沒有這麼費神了。
而在觀察的過程中我編寫了一個模擬的程式（這個。用 python 寫成的，其需要另外安裝 matplotlib 這個模組），可以用來模擬本題的「追逐」。
程式執(zhí)行前可以調(diào) n（裡面命名為 amount）、 k（裡面為 chase）還有一個角色類似 dt 的 stepLength 這三個變數(shù)的值。此程式可以調(diào)「模式」，看你是要觀察這 n 個點在每個時刻所形成的正 n 邊形之樣式（mode = "SHAPE"）、還是要追尋這 n 個點的移動軌跡（mode = "TRACE"）。
除了會畫圖以外，它還會顯示根據(jù) stepLength 而得出的逼近之抵達(dá)時間 nowTime（到中心的一個範(fàn)圍內(nèi)便算做抵達(dá)）。
有興趣或是想要更進(jìn)一步觀察本問題的可以參考上面的鏈結(jié)一下。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
創(chuàng)作回應(yīng)
Not In My Back Yard
這邊的記憶體基本上指的都是「主記憶體」，也就是桌電拆開外殼看到主機(jī)板上、通常位於 CPU 旁邊的 RAM。而不是用來指稱硬碟等其他形式的記憶體裝置。
一般人應(yīng)該不會有到 1TB 的主記憶體啦，至少我周遭的人都沒有。
而記憶體限制代表的是評測系統(tǒng)在編譯後執(zhí)行你的程式時，其所允許的最大記憶體分配量。
以 C 語言為例，一個 long long 型態(tài)變數(shù)之宣告將佔用記憶體空間 8 個 Byte 的空間。而一千萬個 long long 型態(tài)變數(shù)將會佔有 10 ^ 7 × 8 Bytes 約等於 76.3 MB 的記憶體空間。因為本題的限制，所以你不能宣告一千萬個 long long 變數(shù)，在 ZeroJudge 上系統(tǒng)會告訴你 Segmentation Fault（你可以直接想成是分配錯誤）。
所以通常有特殊記憶體限制的題目基本上都是希望你不要用太多的記憶體來達(dá)成題目所求。不過本題的記憶體限制其實挺寬鬆的，所以基本可以當(dāng)作沒有特殊限制。
一般人應(yīng)該不會有到 1TB 的主記憶體啦，至少我周遭的人都沒有。
而記憶體限制代表的是評測系統(tǒng)在編譯後執(zhí)行你的程式時，其所允許的最大記憶體分配量。
以 C 語言為例，一個 long long 型態(tài)變數(shù)之宣告將佔用記憶體空間 8 個 Byte 的空間。而一千萬個 long long 型態(tài)變數(shù)將會佔有 10 ^ 7 × 8 Bytes 約等於 76.3 MB 的記憶體空間。因為本題的限制，所以你不能宣告一千萬個 long long 變數(shù)，在 ZeroJudge 上系統(tǒng)會告訴你 Segmentation Fault（你可以直接想成是分配錯誤）。
所以通常有特殊記憶體限制的題目基本上都是希望你不要用太多的記憶體來達(dá)成題目所求。不過本題的記憶體限制其實挺寬鬆的，所以基本可以當(dāng)作沒有特殊限制。
2021-07-27 03:40:07
Caido
我的作法是挑 i 跟 i+k 兩個點，假設(shè)兩點相距 L，夾角為 θ，可以把 i+k 的速度拆成平行 i 點的速度，這樣他們的相對速度就是 v*(1+cosθ)，總時間就是 L/(v*(1+cosθ))。
https://upload.cc/i1/2021/07/27/V3kj8C.jpg
https://upload.cc/i1/2021/07/27/V3kj8C.jpg
2021-07-27 10:17:50
達(dá)人
