高斯消元(Gaussian Elimination)入门

2018-09-28

数学上,高斯消元法(Gaussian Elimination),是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个行梯阵式。

解多元方程组特别方便。

Read more...


   

以 O(N) 线性时间复杂度递推逆元的方法

2018-08-09

在之前我们已经知道乘法逆元的三种求法,对于一般的题目让你把答案模一个质数,如果要求逆元一般用费马小定理,可以在 \Theta (Nlog_2(N)) 时间内构造出 1 到 N 的逆元:inv(x)=x^{mo-2} \bmod mo。但是对于 10^7 级别的 N,这样的求法就显得有点慢。能不能在 \Theta (N) 时间内递推出 inv(x) 呢?

Read more...


   

利用容斥原理求解 [a,b] 区间中与 n 互质的数字个数(HDU 4135 & ZOJ 3547)

2018-08-08

先看这道丧心病狂的题目:HDU 4135 Co-prime。题目大意就是,有 T 组询问,每组询问给你三个数:a, b, c,问你闭区间 [a,b] 中有多少个数字与 n 互质。数据范围是:1 \leqslant A \leqslant B \leqslant 10^{15}1 \leqslant N \leqslant 10^5

乍一看毫无头绪,仿佛怎么做都会超时……其实用容斥的想法就很容易了~

Read more...


   

欧拉函数 φ(n) 的几个常用性质

2018-07-11

之前我们已经知道欧拉函数 \varphi(n) 的计算公式:

\displaystyle \varphi (n)=n \ast \prod_{i-1}^{r} (\frac {p_i-1} {p_i})

我们还知道它的两条性质:
如果\varphi(x)中的x是质数 p 的 k 次幂,那么 \displaystyle \varphi (x)=\varphi (p^k)=(p-1)p^{k-1}
欧拉函数是积性函数,如果 x 和 y 互质,则 \varphi(xy)=\varphi(x) \varphi(y)=(x-1)(y-1)

今天我们要证明上述性质,再介绍几条新的性质。

Read more...


   

乘法逆元(Multiplicative Inverse Modulo)三种求法总结

2018-07-02

当我们取模的时候,被模数很大,无法直接计算其值,我们就会用取模运算的下面两个性质:

\displaystyle (a+b) \bmod x=((a \bmod x)+(b \bmod x))\bmod x \\
\displaystyle (a\ast b) \bmod x=((a \bmod x)\ast (b \bmod x))\bmod x

那么对于除法,是否也满足这个式子呢?

\displaystyle (a \div b) \bmod x=((a \bmod x)\div (b \bmod x))\bmod x

Read more...


   

欧拉函数、费马小定理与欧拉定理详解

2018-06-24

在数论中,对正整数 n,欧拉函数 \varphi (n) 是小于或等于 n 的正整数中与 n 互质的数的数目。此函数以其首名研究者欧拉命名,它又称为 φ 函数(由高斯所命名)或是欧拉总计函数(totient function,由西尔维斯特所命名)。(来自维基百科)

Read more...