题目链接： 洛谷 BZOJ LOJ 题目大意：这么长的题面，就饶了我吧emmm 这题第一眼看上去没法列出同余方程组。为什么？好像不知道用哪把剑杀哪条龙…… 仔细一看，要按顺序杀龙，所以获得的剑出现的顺序也是固定的。 那么如果能把所有龙杀死，就能模拟出哪把剑杀那条龙了。 （以下设所有除 外的数的最大值为 ） ？ 不，发现这里用剑的限制实际上是给出一个上界，来用lower_bound的。 插入也不要太暴力。我们想到什么？手写平衡树multiset！ 这一部分复杂度是 。 接下来就成了一个同余方程组：。 （ 表示攻击第 条龙的攻击力， 表示第 条龙的血量， 表示第 条龙的恢复能力） 但是好像没那么简单！有一些神奇的情况……要特判！ 在考场上的话我肯定想不到特判任何东西 首先大家应该都知道，等价于 。 但是在这题中不行！你总不能把一头龙的血量凭空减少吧！ 所以 时（题目描述中的特性1不满足时）怎么办？ 我们发现不满足特性1的点都满足 ……也就是只要把他的血量打到小于0就赢了！ 此时答案是 。 另外在所有 时我们解出来的解是0！什么神奇的气功？ 所以这是答案是所有 的 。 至此所有特判结束。 我们一般的EXCRT同余方程组的形式是 。 但是这里有讨厌的 ！更讨厌的是可能没有逆元，不能直接除过去！ 我们来看看如何变形： 此时可以EXGCD解出 的最小正整数解 。 根据某定理（什么定理来着？）可得通解为 。 于是就变成了 。 这一部分复杂度为 。 接下来就是裸的EXCRT了！ 这一部分复杂度为 。 等一下，还有一句提示没看到： 你所用到的中间结果可能很大，注意保存中间结果的变量类型。 突然慌张 冷静分析一下，我们在各种算法中模数都有可能超过int范围，要是一乘…… 那……只能上龟速乘了。时间复杂度是没变，但是常数的话…… 幸好不是wys的题，不然时限就是1s了 好吧，都说完了，上代码吧。 NOI2018D2T1_dragon（EXCRT） 终于啊……https://www.cnblogs.com/1000Suns/p/9608901.html