ARC112F Die Siedler

题意 ： Snuke 使用 种卡玩游戏，卡的编号为 。初始时，Snuke 有 张 号卡。

游戏里有 种卡组，第 种卡组含 号卡的数目为 。

可以进行下列操作任意次：

• 获取一整套卡组。

• 将 张 号牌换成一张 号牌。

求 Snuke 手上牌数的最小值。

， ，时限 。

---

神必题。

特判初始没有牌的情况。

由于换卡总是有收益，不难证明能换就换是最优的。先用这个规则化简 使得 。

我们把所有卡都倒着换成 号卡，个数为 。根据能换就换的原则，这和原问题等价。

然后我们只需考虑仅有 非零的情况，局面的变换转化为了数的变换。

---

记 表示有 个 号牌，通过适当的交换可以得到的最小牌数，容易贪心 求出。

把卡包 也转成一个数 ，使用一次相当于让 加上 。

注意到我们将 换到 再换回 ，可以减少 张牌。

操作后 的可能取值有 ：

能取到当且仅当 有解。根据斐蜀定理，充要条件是

记 ，解集为 ，。

• 当 较大时

直接暴力枚举 并计算 ，复杂度为

• 当 较小时

考虑同余最短路。需要求的是满足 的 的最小值。

记 为满足 的 的最小值。

对于所有 从 向 连边，边权为 ，表示增加一张 号牌。

起点是所有 ， 为 。（注意不能将起点设为 否则 时会出错）

用 BFS ，复杂度为 。

---

哪个算法快用那个，复杂度和 的 的最大因子有关。

接下来就是魔法了！打个表可以发现 的 的因数最大值仅有 ，于是本题就做完了。