算法刷题系列：二分（一）

这个算法竞赛就是个记忆大赛，你做不出来的题说明你没做过同类型或者同个模型的题，当然不是你的智商有问题，所以多做题很重要，加油！

一、糖果促销

码题集：糖果促销

第一种当然是自己最开始想到的，那么就是这个你买多少糖，那么你能最后通过换取最终得到的糖也就多，这显然是单调的，所以我想到了二分，然后就是判断在满足条件下，最小的那一个就行了，然后就套模板，写个check就行了，值得注意的是，当p为1时，check里会无限循环，所以得特判一下。
当然也可以直接用数学思维 k -= (k-1) / p，这当然我是想不到，反正这个算法竞赛就是个记忆大赛，你做不出来的题说明你没做过同类型或者同个模型的题，当然不是你的智商有问题，加油！

#include <cstdio>
#include <iostream>

using namespace std;
int T, p, k;

bool check(int v)
{
    int res = v;
    while(v / p)
    {
        res += v / p;
        v = v % p + v / p;
    }

    return res >= k;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &p, &k);
        if(p == 1)
        {
            printf("%d\n", (bool)k);
            continue;
        }

        int l = 0, r = k;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        printf("%d\n", l);
    }
}