警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「NOI 2018」屠龙勇士 - exCRT

生地很自闭,哭着回来搞 OI 了 >_<。

题意

\(\{a\},\{p\},\{k\}\),求解

\[ \left\{\begin{array}{ccc} a_1-x\cdot k_1 & \equiv & 0\pmod{p_1} \\ a_2-x\cdot k_2 & \equiv & 0\pmod{p_2} \\ & \vdots & \\ a_n-x\cdot k_n & \equiv & 0\pmod{p_n} \\ \end{array}\right. \]

解法

显然原方程组可以化成

\[ \left\{\begin{array}{ccc} a_1x & \equiv & b_1\pmod{p_1} \\ a_2x & \equiv & b_2\pmod{p_2} \\ & \vdots & \\ a_nx & \equiv & b_n\pmod{p_n} \\ \end{array}\right. \]

的形式。

\(x\) 出现系数时,普通 exCRT 就用不了了。

所以要用 ex-exCRT

假设我们已知前 \(k-1\) 个方程的方程组的通解为 \(x+t\cdot m\)

那么将其作为未知数代入第 \(k\) 个方程,即 \(a_kx + t\cdot a_km\equiv b_k\pmod{p_k}\)

移项得 \(t\cdot a_km\equiv b_k-a_kx\pmod{p_k}\)\(t\cdot a_km+y\cdot p_k=b_k-a_kx\)

所以只要用 exgcd 求解就好了。

解出来 \(t\) 就可以得到前 \(k\) 个方程的方程组的一个解为 \(x+t\cdot a_km\),然后又可以推出通解,继续迭代即可。

  1. 首先同一种攻击力可能出现多次,所以要用 multiset
  2. 每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑,则选择攻击力最低的一把剑作为武器。

upper_bound 会返回在指定区间内第一个比它大的元素。那么 --upper_bound 就是我们所需要的答案。

注意必须要特判 upper_bound 等于 begin 的情况。

  1. 建议 #define int long long,爆 long long 太毒瘤了……

  2. 直接写只有 \(70\) 分。因为另外 \(30\%\) 数据不满足 \(a_i\le p_i\) 但是满足 \(p_i=1\)

答案显然为 \(\max\left\{\left\lceil\frac{a_i}{k_i}\right\rceil\right\}\)

代码