zcmimi's blog

arrow_backexgcd共3篇文章

avatar
zcmimi
2019-01-21 11:31:55

转自https://www.cnblogs.com/hadilo/p/5914302.html

欧几里得

定义:

gcd(a,b)为整数ab的最大公约数

引理:

gcd(a,b)=gcd(b,a \bmod b)

证明:

设$r=a \b

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-02-18 17:27:00
查看原题

点击跳转

  1. 快速幂
  2. Exgcd

    xy \equiv z \pmod p

    yx+pb = z

    可以用Exgcd求解

  3. bsgs

    求解关于x的方程:

    y^x \equiv z \pmod p

    其中\gcd(y,p)=1

    解法:

    x=am-b

    那么y^{am} \equiv z \cdot y^b \pmod p

    右边:

    枚举b的取值[0,m-1],计算右边的值,存入哈希表

    左边:

    枚举可能的a,也就是[1,m],若左边的值在哈希表中出现过,那么当前a合法

    不难证明当m=\sqrt p的时候复杂度最优,\Theta(\sqrt p)

1/1
Search
search