CF1699E Three Days Grace

给定一个初始有 $n$ 个元素的可重复集合 $A$，其中每个元素都在 $1$ 到 $m$ 之间。 每次操作可以将 $A$ 中的一个元素（称之为 $x$）从 $A$ 中删除，然后在 $A$ 中加入两个元素 $p,q$，满足 $p\cdot q=x$ 且 $p,q>1$。 显然每次操作后 $A$ 的大小会增加 $1$。 定义 $A$ 的平衡值为 $A$ 中的最大值减去最小值，求任意次操作（可以是 $0$ 次）后最小可能的平衡值。

无

无

In the first test case, we can apply the operation on each of the $ 4 $ s with $ (p,q) = (2,2) $ and make the multiset $ \{2,2,2,2,2,2,2\} $ with balance $ \max(\{2,2,2,2,2,2,2\}) - \min(\{2,2,2,2,2,2,2\}) = 0 $ . It is obvious we cannot make this balance less than $ 0 $ . In the second test case, we can apply an operation on $ 12 $ with $ (p,q) = (3,4) $ . After this our multiset will be $ \{3,4,2,3\} $ . We can make one more operation on $ 4 $ with $ (p,q) = (2,2) $ , making the multiset $ \{3,2,2,2,3\} $ with balance equal to $ 1 $ . In the third test case, we can apply an operation on $ 35 $ with $ (p,q) = (5,7) $ . The final multiset is $ \{6,5,7\} $ and has a balance equal to $ 7-5 = 2 $ . In the forth test case, we cannot apply any operation, so the balance is $ 5 - 1 = 4 $ .