#P10447. [2021年联测]包装

[2021年联测]包装

包装(package)

题目描述

有 nn 位顾客,他们将各自购买相同数量的商品,但购买量尚未确定,可能是 1,2,…,m1,2,\ldots,m 中任意整数。

需要提前准备一批装好的箱子,每箱装非负整数件商品。无论最终购买量为多少,都应能把一些箱子分给这 nn 位顾客,使每位顾客得到的商品总量恰好等于购买量;一只箱子只能给一位顾客,箱子不能拆开,可以有箱子不使用。

求最少需要准备多少只箱子。

形式化地,求非负整数多重集 SS 的最小大小,使得对每个 1≤i≤m1\le i\le m,都能从 SS 中取出 nn 个彼此不共用元素副本的子多重集,各自元素和均为 ii。不同 ii 的分配方案分别考虑,始终使用同一批预先准备的箱子。

输入格式

一行两个正整数 n,mn,m。

输出格式

输出一个非负整数,表示最少箱子数。

样例 1 输入

5 8

样例 1 输出

15

样例说明

一种合法准备方案是

S={1,1,1,1,1,2,2,2,3,3,4,5,6,7,8}.S=\{1,1,1,1,1,2,2,2,3,3,4,5,6,7,8\}.

数据范围

全部数据满足 1≤n≤1061\le n\le10^6,1≤m≤10141\le m\le10^{14}。

子任务 分值 附加限制
1 20 n,m≤10n,m\le10
2 n,m≤5000n,m\le5000
3 n,m≤105n,m\le10^5
4 n≤105n\le10^5,m≤109m\le10^9
5 10 n≤105n\le10^5,m≤1014m\le10^{14}
6 n≤106n\le10^6,m≤1013m\le10^{13}