b936: Kevin 愛橘子

內容

有一天 Kevin 走在路上，隨手摘了一顆路邊樹上的橘子
當他正準備咬下去時，忽然一個瞬間他停了下來
一看不得了，這顆橘子裡面竟然有 N 片橘子！
這讓 Kevin 很苦惱，因為他昨天看到電視上說人一天只需要吃 M 片橘子就能攝取到足夠的營養
他不想要獨享這顆橘子，他希望能讓越多的人能至少吃到 M 片橘子
但是由於 Kevin 走在路上甚麼都沒帶，因此他每次只能將橘子分成兩半

例如若要分一顆有 N 片的橘子
當 N 為偶數，則 Kevin 會將其分成 N/2 和 N/2 兩堆
當 N 為奇數，則 Kevin 會將其分成 (N-1)/2 和 (N+1)/2 兩堆

譬如當橘子有 10 片時，他會將橘子分成 5 片和 5 片
而當橘子有 11 片時，他會將橘子分成 5 片和 6 片

再說了這麼多之後，你身為 Kevin 的朋友，早就已經餓的望著橘子發楞了
但是 Kevin 還沒決定好總共到底有多少人能夠吃到橘子
為了趕快吃到橘子，你能幫幫 Kevin 嗎？

輸入

多筆輸入 保證輸入筆數 < 10^6
每行有兩個數字 N 和 M
代表一顆裡面有 N 片的橘子
和 Kevin 希望每個人都至少能夠吃到 M 片橘子
1 <= N <= 10^15
1 <= M <= 10^15

2 1
10 3
12 3
1024 2
201612 28

輸出

請輸出這顆橘子總共可以分給多少人並滿足 Kevin 的要求
(人數包含 Kevin)

2
2
4
512
4096

解題思路

用遞迴模擬 Kevin 剝橘子的過程直到要剝的那片除 2 時小於目標大小時返回 1。

ZJ 改版之後伺服器似乎變弱很多，同樣的程式碼舊版 0.9s 過的放到現在要 1.7s，這導致這題時間變得比較緊張，善用位元運算加速。

完整程式碼

AC (1.7s, 116KB)

#include <stdio.h>

long long n, m;

long long dfs(long long piece)
{
    if ((piece >> 1) < m)
        return 1;
    if (piece & 1)
        return dfs((piece + 1) >> 1) + dfs((piece - 1) >> 1);
    else
        return dfs(piece >> 1) << 1;
}

int main()
{
    while (scanf(" %lld %lld", &n, &m) == 2)
    {
        printf("%lld\n", n < m ? 0 : dfs(n));
    }
    return 0;
}