生地很自闭,哭着回来搞 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. \]

阅读全文 »

简介

CRT 可以在 \(b_1\cdots b_k\) 两两互质时,解出形如

\[ \left\{\begin{array}{ccc} x & \equiv & a_1\pmod{b_1} \\ x & \equiv & a_2\pmod{b_2} \\ & \vdots \\ x & \equiv & a_k\pmod{b_k} \end{array}\right. \]

的方程组。

阅读全文 »

简介

数论只会 GCD 说的就是我了……

exgcd 可以解出形如 \(ax+by=\gcd(a,b)\) 的方程的一组解。

其实可以解出 \(\enclose{horizontalstrike}{ax+by=c}\),因为 \(\enclose{horizontalstrike}{c\ne\gcd(a,b)}\) 时无解

阅读全文 »

简介

BSGS 可以在 \(O(\sqrt n)\) 的时间内,解出形如 \(a^x\equiv b\pmod P\)\(x\)

普通 BSGS 只能处理 \(\gcd(a,P)=1\) 的情况,使用 exBSGS 可以处理任意 \(a, n, P\) 的数据。

不会 exBSGS,于是咕咕了(

阅读全文 »

题意

传送门:洛谷 P5280 - 线段树

你要维护一堆区间 \([1, n]\) 的线段树,最开始只有一棵树,而且是空的。支持两种操作:

  1. 把这堆线段树翻倍,把第 \(i\) 棵复制成 \(2i\)\(2i+1\),并给所有编号为奇数的线段树中的区间 \([l, r]\) 打上 lazy tag。
  2. 查询所有的线段树中打上 lazy tag 的节点数。
阅读全文 »