zcmimi's blog

arrow_back数论共123篇文章

avatar
zc
2020-03-10 22:33:00
查看原题

点击跳转

题意:

G^{\sum d|{N\choose d}}\bmod 999911659

1 \le G \le 10^9,1 \le N \le 10^9

999911659是质数,根据欧拉定理:

G^{\sum d|{N\choose d}}\bmod 999911659 = G^{\sum d|{N\choose d} \bmod 999911658}\bmod 999911659

关键求\sum d|{N\choose d} \bmod 999911658

模数太大,直接lucas取模会炸

我们可以考虑将模数分解质因数

999911658=2\times 3 \times 4679 \times 35617

可以用lucas枚举约数算出

\begin{cases} a_1=\sum d|{N\choose d} \pmod 2 \\ a_2=\sum d|{N\choose d} \pmod 3 \\ a_3=\sum d|{N\choose d} \pmod {4679} \\ a_4=\sum d|{N\choose d} \pmod {35617} \end{cases}

然后通过crt求:

\begin{cases} x \equiv a_1 \pmod 2 \\ x \equiv a_2 \pmod 3 \\ x \equiv a_3 \pmod {4679} \\ x \equiv a_4 \pmod {35617} \end{cases}

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-08 10:54:00
查看原题

点击跳转

K^x \equiv 1 \pmod M

求最小的非负整数x

最近刚学了bsgs,一眼看成exbsgs

exbsgs可以,但是比较麻烦

看到最后是1,我们可以想到欧拉定理:

K^{\varphi(M)} \equiv 1 \pmod M(\gcd(K,M)=1)

可以发现,答案是\varphi(M)的约数,那么枚举\varphi(M)的约数即可(可以一直尝试枚举删掉约数)

\gcd(K,M)!=1时无解

avatar
zc
2020-03-07 21:58:00
查看原题

点击跳转

\overbrace{111\dots111}^{\text{N个1}} \equiv k \pmod m \\ \frac{10^N-1}9\equiv k \pmod m \\ 10^N\equiv 9k+1 \pmod m

顺利地推出是bsgs,(m是质数,也就不用exbsgs了)

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

avatar
zc
2020-02-25 17:16:00
查看原题

点击跳转

bsgs模板题

avatar
zc
2020-02-24 13:59:00
查看原题

点击跳转

我们要做的是强行将式子转换为bsgs能求解的形式(求y^x\equiv z \pmod p)

X_{i+1} \equiv aX_i+b \pmod p \\ X_{i+1} + \frac ba \equiv aX_i+b+\frac ba \pmod p \\ aX_{i+1} + b \equiv a^2X_i+ab+b \pmod p \\ X_{i+2} \equiv a^2X_i+ab + b \pmod p

继续往下推,并根据等比数列的公式可以得到:

X_i \equiv a^{i-1}X_1+\frac{b(1-a^{i-1})}{1-a} \pmod p

带入t\equiv X_i \pmod p,得

t \equiv a^{i-1}X_1+\frac{b(1-a^{i-1})}{1-a} \pmod p \\ (1-a)t \equiv (1-a)a^{i-1}X_1+b(1-a^{i-1}) \pmod p \\ t-at \equiv a^{i-1}(X_1-aX_1)+b-b\cdot a^{i-1} \pmod p \\ a^{i-1}(X_1-aX_1-b)\equiv t-at-b \pmod p \\ a^{i-1}\equiv \frac{t-at-b}{X_1-aX_1-b} \pmod p

成功强行转换

可以用bsgs求解了!

还没完,要考虑一下几种特殊情况:

  1. X_1=t

    第一天就可以读到

  2. a=1

    题目变为X_1+kb \equiv t \pmod p

    因为p是质数,所以可以直接用费马小定理求逆元

    b=0时无解

  3. a=0

    判断b=t

avatar
zc
2020-02-18 21:05:00
查看原题

点击跳转

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)

9/13
Search
search