#2166. 猴子吃桃子

猴子吃桃子

题目描述

nn 个可爱的小猴子,有一天,妈妈摘了 mm 个桃子,可是怎么分都分不平均。于是妈妈偷偷地把桃子藏了起来,准备第二天再想办法。

可是孩子们到了晚上,纷纷去偷吃。第一只猴子去的时候发现把桃子分成 nn 份相等的量,会剩下 11 个桃子,于是拿走了自己的一份,并把多余的 11 个桃子也拿走了。第二只猴子去的时候发现平分成 nn 份时会剩下 22 个桃子,于是拿走了自己的一份,并把多余的 22 个桃子也拿走了……第 kk 只猴子去的时候发现平分成 nn 份时会剩下 kk 个桃子,于是拿走了自己的一份,并把多余的 kk 个桃子也拿走了,第 k+1k+1 只猴子去的时候发现平分成 nn 份后只剩下 11 个桃子,于是拿走了自己的一份,并拿走了多余的 11 个桃子,第 k+2k+2 只猴子去的时候发现平分成 nn 份后剩下 22 个桃子,于是拿走了自己的一份,并拿走了多余的 22 个桃子……如此 kk 个一循环。第 nn 个猴子去的时候,把剩下的桃子(至少一个)全都吃了。

试问 mm 至少是多少? 任务:输入正整数 n,k(k<n)n,k(k<n),求出最小的正整数 mm,桃子不能分割。

输入格式

输入仅包含一行,包括两个用空格隔开的正整数 n,kn,k

输出格式

输出一个正整数,表示最小的 mm,答案有可能超过 2642^{64}

样例输入

4 3

样例输出

73

数据规模与约定

30%30\% 的数据满足:0<k<n<120<k<n<12

另外 15%15\% 的数据满足:k+1=nk+1=n

100%100\% 的数据满足:0<k<n<1000<k<n<100