2020-07-22

a new method of knapsack problem : if the volumes of objects are power-related and # of items are unlimited,we can calculate it by simple dp or the sense of combinatory

Number Thoery Learning Notes

1.费马小定理

$a^b\equiv a^{b\bmod (p-1)}\pmod p$
$st.\; p \; is \; a \; prime$

2.欧拉定理

$a^b\equiv a^{b\bmod φ(m)}\pmod m$
$st.\ m \ and \ a\ are\ coprime$

3.扩展欧拉定理

$\left\{\begin{matrix} \ a^b ,b\leqφ(m)\\ \ a^{b\bmodφ(m)+φ(m)},b>φ(m) \end{matrix}\right.$
$st.for\ all\ a\ and\ m$

proof of 欧拉定理

构造 $p_i=a*x_i\ \{gcd(x_i,m)=1\}$
$p_i$ 两两不同，且有 $φ(m)$ 种取值，则 $a^{φ(m)}\equiv1 \pmod m$