P7851.md

「JZOI-2」信号塔

题目描述

在一条有 $10^{999}+1$ 个点的直线上，满足直线上相邻两点间的距离相等，每个点上建立都建立了一个信号塔，从左到右编号为 $0\sim 10^{999}$，其中 $0$ 号塔是电视节目发送点。

由于小僖只想看电视，所以这里的信号只会从左往右传输。假设一个信号塔的强度为 $x$，那么它的信号最多能往右传输 $\lfloor\frac{x-1}{k}\rfloor$ 的距离。

现在小僖要给每个信号塔设置一个强度，但由于信号塔太多了，他忙不过来，于是他交给了笨笨机器人来做。

笨笨机器人按照以下方式给每个信号塔设置一个强度。

首先先将 $0$ 号塔的强度设为 $10^{30}$，然后从左到右，从 $1$ 号信号塔开始一直做到 $10^{999}$ 号信号塔。对于每个信号塔，在其左边寻找离它最近的一个信号塔 $a$，满足 $a$ 信号塔的信号可以传送到该信号塔，然后将该信号塔的信号强度赋值为这两个信号塔之间的距离。

这里定义 $i$ 号信号塔和 $j$ 号信号塔之间的距离为 $|i-j|$。

例如当 $k=2$ 的时候 $1\sim5$ 号的信号塔的强度分别为 $1,2,3,1,5$。

但小僖还是不放心笨笨机器人，所以他想知道第 $n$ 个信号塔的强度。

输入格式

一行，两个正整数 $n,k$。

具体意义见题面。

输出格式

一行，一个整数，表示编号为 $n$ 信号塔的强度。

样例 #1

样例输入 #1

1 1

样例输出 #1

1

样例 #2

样例输入 #2

5 2

样例输出 #2

5

提示

对于 $10%$ 的数据，$1\le n,k\le 2 \times 10^3$。
对于 $30%$ 的数据，$1\le n\le 1 \times 10^7$。
对于另外 $15%$ 的数据，$k=1$。
对于另外 $15%$ 的数据，$k=2$。
对于 $100%$ 的数据 $1\leq n\leq10^{18},1\leq k\leq10^{6}$。