由于中考数学没考满分,所以我认识到自己不会数学。
rt,挑战一天学两个板子。
EXCRT
比 CRT 简单。
考虑同余方程组 {x≡A1(modB1)x≡A2(modB2)\begin{cases}x\equiv A_1 \pmod{B_1}\\x\equiv A_2 \pmod{B_2}\end{cases}{x≡A1 (modB1 )x≡A2 (modB2 ) 。
显然 xxx 的值为 k1B1+A1=k2B2+A2=xk_1B_1+A_1=k_2B_2+A_2=xk1 B1 +A1 =k2 B2 +A2 =x 的任意解,其中 k1,k2k_1,k_2k1 ,k2 也是未知数。
移一下项,k1B1−k2B2=A2−A1k_1B_1-k_2B_2=A_2-A_1k1 B1 −k2 B2 =A2 −A1 。
显然符合 exgcd 的形式。
解出任意一个 k1k_1k1 ,则原方程组就等价于方程 x≡k1B1+A1(modgcd(B1,B2))x\equiv k_1B_1+A_1\pmod {\gcd(B_1,B_2)}x≡k1 B1 +A1 (modgcd(B1 ,B2 ))。
逐一合并即可。
输入是反着的;实现时开 __int128;实时取模,否则你得开 int256。
时间复杂度:O(nlogV)O(n\log V)O(nlogV)。
高斯消元
就普通解方程的方法,你平常咋解方程就咋写,嗯对。反正能做到 O(n3)O(n^3)O(n3)。
然后这个竟然可以求逆矩阵?!
求证:若矩阵 X=A,Y=IX=A,Y=IX=A,Y=I 同时进行相同的矩阵初等变换后,若 X=IX=IX=I,则此时 Y=A−1Y=A^{-1}Y=A−1。
证明:
假设 B=A−1B=A^{-1}B=A−1。则我们可以将两矩阵的关系表示为 XB=YXB=YXB=Y。
由矩阵乘法定义得,在经过一次相同的矩阵初等变换后,依然满足 XB=YXB=YXB=Y 的关系,自行证明不难。
嗯。
时间复杂度:O(n3)O(n^3)O(n3)。