zcmimi's blog

arrow_backexcrt共3篇文章

avatar
zc
2020-03-08 23:30:00
查看原题

点击跳转

先预处理出每次的攻击力c_i,推荐使用multiset

问题变成了:

c_ix \equiv a_i \pmod{p_i}

可是题目并没有保证a_i\le p_i

仔细阅读题目,可以发现当a_i>p_i的时候一定满足p_i=1

那么在这个情况答案就是\max_{i=1}^n(\left \lceil \frac{a_i}{c_i} \right \rceil)

接下来就是a_i \le p_i的情况了

标准的Excrt要求x的系数必须为1

我们可以转化为Exgcd解不定方程

c_ix \equiv a_i \pmod{p_i}

c_ix + p_iy = a_i

可以用Exgcd解出一组解sx,sy,并得出

x=sx+\lambda \frac{p_i}{\gcd(c_i,p_i)}

也就是

x\equiv sx \pmod{\frac{p_i}{\gcd(c_i,p_i)}}

这样就可以用Excrt求解了

特判:

  1. 所有a_i=p_i,那么所有sx=0,按照上面的方法解是不对的(答案会等于0)

    直接求出杀死每条龙所需的刀数然后所有刀数求一个lcm即可

    也就是lcm_{i=1}^n(\frac{p_i}{\gcd(c_i,p_i)})

  2. c_ip_i的倍数的时候杀不死这条龙

    但这时如果a_i=p_i,这个方程相当于没用,可以换成x \equiv 0 \pmod 1之类的

记得全部开long long,用龟速乘

avatar
zc
2020-03-08 10:57:00
查看原题

点击跳转

avatar
zc
2020-03-07 20:32:00
查看原题

点击跳转

扩展中国剩余定理

给定方程组:

\begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \\ x\equiv a_2\ ({\rm mod}\ m_2) \\ ... \\ x \equiv a_n\ ({\rm mod}\ m_n) \end{cases}

求最小的非负整数x

假设我们求出了前i-1组的解x_{i-1}

M=\operatorname{lcm}(m_1,m_2,\cdots,m_{i-1})

x_{i-1}+\lambda M \equiv a_{i-1} \pmod{m_{i-1}}(\lambda \in \Z)

那么我们需要求出最小的非负整数t使:

x_{i-1}+tM\equiv a_i \pmod{m_i}

也就是Mt\equiv a_i-x_{i-1} \pmod{m_i}

可以使用Exgcd求解t (ax\equiv c \pmod b)

如果无解,则整个方程误解

若有解,x_i=x_{i-1}+tM

1/1
Search
search