#P10447. [2021年联测]包装
[2021年联测]包装
包装(package)
题目描述
有 位顾客,他们将各自购买相同数量的商品,但购买量尚未确定,可能是 中任意整数。
需要提前准备一批装好的箱子,每箱装非负整数件商品。无论最终购买量为多少,都应能把一些箱子分给这 位顾客,使每位顾客得到的商品总量恰好等于购买量;一只箱子只能给一位顾客,箱子不能拆开,可以有箱子不使用。
求最少需要准备多少只箱子。
形式化地,求非负整数多重集 的最小大小,使得对每个 ,都能从 中取出 个彼此不共用元素副本的子多重集,各自元素和均为 。不同 的分配方案分别考虑,始终使用同一批预先准备的箱子。
输入格式
一行两个正整数 。
输出格式
输出一个非负整数,表示最少箱子数。
样例 1 输入
5 8
样例 1 输出
15
样例说明
一种合法准备方案是
数据范围
全部数据满足 ,。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 20 | |
| 2 | ||
| 3 | ||
| 4 | , | |
| 5 | 10 | , |
| 6 | , |