既然有心想解,請務必有耐心
整體概念就是幫水桶裝水,
當不斷將n加上1時,
加上去的1平均分配給每桶水,
且水桶的數量使得n=m*2^?+??,
同時保有最大值(至少 >= 2^?)。
今已知n為m*2^?+??,
求得? = (n/m最多可以除2幾次),
然後2^?將成為基礎數量(就是已經裝滿到m水量的水桶),
而??的數值會平均再分配給2^?(那些已經裝滿到m水量的水桶)
以這個基礎數量去加上後來又裝滿到2m水量的水桶數量即為答案,
當n=m*2^?+(m*2^? - 2^?)時,
??=(m*2^? - 2^?),
各個水桶即將裝滿到2m,
此時n每每往上加1,
都會再均分出一桶裝滿m水量的水桶,
加1的狀態持續直到n=m*2^(?+1)時停止。
-------------------------
總結,答題流程不使用遞迴,這次也沒用到位元運算bitset,
可以直接用long long p = ( log2(n)-log2(m)+0. 000 000 000 000 001 )取得?是多少,
這裡必須要做到小數點後十五位修正,十分刁鑽!
接著求得2^?的數值,我使用快速冪實作,
最後印出2^? + (?? - 2^?)就大功告成
Fp = 2^?
化簡:Fp + ( n%(m*Fp) - m*Fp ) = Fp-m*Fp+n%(m*Fp)
輸入輸出全部scanf和printf下去,然後記得全部使用long long
引入的標頭檔案:
<stdio.h>用在scanf, printf
<math.h>用在log2(n) - log2(m)
程式架構:
快速冪副函式共7行(外框3行,內碼4行)
主程式共10行(外框3行,內碼7行)
執行結果:(0.4s, 140KB)
期望你也做得到ouob
--------------------------
以下是窮舉推敲的過程
6 = 3*2^1>>2
7 = 3*2^1...1>>2
8 = 3*2^1...2 >>2
9 = 3*2^1...3>>2
10 = 3*2^1...4 >>2 每桶水皆差1即滿溢到可以再均分為兩桶水,共有2^?桶水,?=1
11 = 3*2^1...5>>3 該階段滿溢開始(第一桶)
12 = 3*2^2>>4 該階段滿溢結束(第2^?桶也是最後一桶,?=1)
13 = 3*2^2...1>>4
14 = 3*2^2...2>>4
15 = 3*2^2...3>>4
16 = 3*2^2...4>>4
17 = 3*2^2...5>>4
18 = 3*2^2...6>>4
19 = 3*2^2...7>>4
20 = 3*2^2...8>>4 每桶水皆差1即滿溢到可以再均分為兩桶水,共有2^?桶水,?=2
21 = 3*2^2...9>>5 該階段滿溢開始(第一桶)
22 = 3*2^2...10>>6
23 = 3*2^2...11>>7
24 = 3*2^3>>8 該階段滿溢結束(第2^?桶也是最後一桶,?=2)
25 = 3*2^3...1>>8
.
.
.