#L23008. 保证k人住进同一间

    ID: L23008 传统题 2000ms 128MiB 尝试: 0 已通过: 0 入门 上传者: 标签>M2M2第二学期M2-第30课模运算与周期余数只有这么多间房余数类与抽屉原理课堂题

保证k人住进同一间

保证k人住进同一间

题目描述

所有整数按模 m 分成 m 个余数类。求至少任取多少个整数,才能保证其中存在 k 个数属于同一余数类。所取整数允许数值重复。

输入格式

一行输入 m、k,满足 1≤m,k≤10^9。

输出格式

输出保证成立的最少数量 m(k-1)+1。k=1时答案为1。

样例

输入

5 4

输出

16