主題
題目連結(jié)：
題目大意：
輸入有多列，每列給定兩正整數(shù) n 、 k。代表著 Peter 原先有 n 支菸，每支菸抽完後會(huì)有一份菸屁股，每 k 份菸屁股可以?huà)猿梢恢碌妮巍?/div>
試問(wèn) Peter 最多可以抽多少支菸？
範(fàn)例輸入：
4 3
10 3
100 5
範(fàn)例輸出：
5
14
124
解題思維：
本題模擬即可—— n 支菸抽完後變成 n 份菸屁股，每 k 份換一支新的菸然後抽掉變成菸屁股，重複此步驟直到手頭有的菸屁股數(shù)量 < k。途中抽的菸數(shù)即是所求。
不過(guò)，本題有著一個(gè)神祕(mì)的公式解，即所求 =
n + floor((n - 1) ÷ (k - 1))
其中 floor() 代表下高斯，即向下取整（對(duì)於正的數(shù)字來(lái)說(shuō)即無(wú)條件捨去）。
原本模擬的過(guò)程，其等價(jià)於求下式
n + floor(n ÷ k) + floor(n ÷ (k ^ 2)) + ……
但是難以（至少需要寫(xiě)不少步驟）證明其等價(jià)於公式。
不過(guò)，實(shí)際上有一個(gè)相當(dāng)精巧的文字?jǐn)⑹鲋C明，其內(nèi)容如下：
我們將原先的 n 支菸抽掉得到 n 份菸屁股。
此時(shí)，我們先拿走一個(gè)菸屁股，因此剩下 n - 1 份菸屁股。
因?yàn)槊?k 份菸屁股可以組成一支菸，因此我們接著從 n - 1 份菸屁股裡拿走 k - 1 份菸屁股與剛剛預(yù)先拿走的那一份菸屁股組合成一支菸然後抽掉。抽掉之後，會(huì)留下一份菸屁股。
而留下的菸屁股就仿照上述的做法，從剩下的菸屁股堆拿 k - 1 份與該份組合並抽掉。抽掉之後又會(huì)剩下一份菸屁股。因此，我們就重複此步驟直到菸屁股堆的數(shù)量不足 k - 1 為止。
因此，過(guò)程中抽的菸數(shù)恰好為
n + floor((n - 1) ÷ (k - 1))
得證。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
達(dá)人
