[ZJ b936] b936: Kevin 愛橘子

 原題： b936. Kevin 愛橘子 - 高中生程式解題系統 (zerojudge.tw)

解題方向：觀察

題目要求把 $n$ 不斷剖半 ( 遇到奇數就分成 $x,x+1$ )，問至少能分成幾塊，使每一塊大小至少為 $m$ 。

假設 $n \geq m$：

很顯然的，如果 $n=m\times 2^{k}$ ，答案為 $2^{k}$ 。

因此，我們要來討論 $n=m\times 2^{k}+r$，的情形，當中 $1\leq r < m\times 2^{k}$ 

根據觀察可以發現，每當 $r$ 增加 $2^{k}$ ，所有最後切下的部位就會增加 $1$：

比如說 

$n=25,m=6$ 時，會得到切除的結果是 $\{7,6,6,6\}, r=1$

$n=26,m=6$ 時，會得到切除的結果是 $\{7,7,6,6\}, r=2$

$n=27,m=6$ 時，會得到切除的結果是 $\{7,7,7,6\}, r=3$

$n=28,m=6$ 時，會得到切除的結果是 $\{7,7,7,7\}, r=4$

$n=29,m=6$ 時，會得到切除的結果是 $\{8,7,7,7\}, r=5$

因此，我們可以發現，當 $r\leq (m-1)\times 2^k$ 時，不影響答案，但是當 $r$ 大於 $ (m-1)\times 2^k$ 時，就會讓增加的項可以被近一步分割 !

比如說 

$n=43,m=6$ 時，會得到切除的結果是 $\{11,11,11,10\}, r=19$

$n=44,m=6$ 時，會得到切除的結果是 $\{11,11,11,11\}, r=20$

$n=45,m=6$ 時，會得到切除的結果是 $\{6,6,11,11,11\}, r=21$

原本是 $12$的項能被近一步分解為 $6,6$，因此分割數加了。

故我們可以得到下公式

$n = m\times 2^{k}+r$

$f(n)=\begin{cases}2^k&0\leq r\leq (m-1)\times 2^k\\2^k+t&(m-1)\times 2^k+t=r& t>0\end{cases}$

故得證。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll n, m;
    while (~scanf("%lld%lld", &n, &m)) {
        if (n<m) {
            puts("0");
            continue;
        }

        long long P = 0;
        for(int i=0;n>=m*(1LL<<i);i++) {
            P = i;
        }
        long long R = n - m*(1LL<<P);

        long long ans = 1LL<<P;
        if (R > (m-1) * (1LL<<P))
            ans += R - (m-1) * (1LL<<P);

        printf("%lld\n", ans);

    }
    return 0;
}