BZOJ-1192-鬼谷子的錢袋

描述

鬼谷子非常聰明，正因為這樣，他非常繁忙，經常有各諸侯車的特派員前來向他咨詢時政。有一天，他在咸陽游歷的時候，朋友告訴他在咸陽最大的拍賣行（聚寶商行）將要舉行一場拍賣會，其中有一件寶物引起了他極大的興趣，那就是無字天書。但是，他的行程安排得很滿，他他已經買好了去邯鄲的長途馬車標，不巧的是出發時間是在拍賣會快要結束的時候。于是，他決定事先做好準備，將自己的金幣數好并用一個個的小錢袋裝好，以便在他現有金幣的支付能力下，任何數目的金幣他都能用這些封閉好的小錢的組合來付賬。鬼谷子也是一個非常節儉的人，他想方設法使自己在滿足上述要求的前提下，所用的錢袋數最少，并且不有兩個錢袋裝有相同的大于1的金幣數。假設他有m個金幣，你能猜到他會用多少個錢袋，并且每個錢袋裝多少個金幣嗎？

---

分析

• 可能有點水, 但這種題做的很少, 還是練習一下比較好
• 考慮二進制
• 任何數都可用2的冪次方加和得到.
• 那么把m個金幣拆成幾個2的冪次方的數就可以湊出任何 1~m 之間的數了. 但是不一定會正好, 把剩下的錢拆成單獨一份, 答案就是第一個大于m的2^n的那個n. 那如果正好拆完呢? 因為最后一份不可以是m, 所以還是要把m拆開, 結果還是一樣.
• 為什么是二進制不是其他進制呢? 因為任何數都可用2的冪次方加和得到. 但其他的就不一定了.

---

代碼

https://code.csdn.net/snippets/612326