---
tags: 數論, prime number, 最大公因數 gcd, 模反元素, 中國剩餘定理 CRT
---
# 數論
## 質因數
### 質因數排組
$X=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times ...\times p_n^{a_n}$
* $X$的因數個數＝$(a_1+1)\times (a_2+1)\times (a_3+1)\times ...\times (a_n+1)$
* $X$的因數總和＝$(\sum\limits_{i=0}^{a_1}p_1^{i})\times (\sum\limits_{i=0}^{a_3}p_2^{i})\times (\sum\limits_{i=0}^{a_3}p_3^{i})\times ...\times (\sum\limits_{i=0}^{a_n}p_n^{i})$
### 篩法
#### 作法
* 從2開始把2的倍數刪掉，再把還沒被刪掉的最近的數(i.e 3)的倍數刪掉，依序往下刪除剩下的數為質數

#### 複雜度
$\frac{n}{2}+\frac{n}{3}+\frac{n}{5}+...+\frac{n}{p}$
$\le\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+...+\frac{n}{n}$
$\le\frac{n}{1}+[\frac{n}{2}+\frac{n}{2}]+[\frac{n}{4}+\frac{n}{4}+\frac{n}{4}+\frac{n}{4}]+...$
$=nlogn$

* **$O(nlogn)$**

---
## 最大公因數 GCD
### 求GCD的方法
* $gcd(a, b)=gcd(b, {a\ mod\ b})$
#### 複雜度
* $O(log \min(a, b))$
### 求$ax+by=gcd(a,b)$
#### 解法
$\begin{equation}
\left\{
\begin{array}{l}
(a,\ b)=(x_1,\ y_1) & \\
(b,\ a\ mod\ b)= (x_0,\ y_0)
\end{array}
\right.
\end{equation}$

$bx_0+(a\ mod\ b)y_0=gcd(a,\ b),\ 且\ x_0=gcd(a,b),\ y_0=0$
$bx_0+(a-kb)y_0=gcd(a,\ b)$
$a(-y_0)+b(x_0-ky_0)=gcd(a,\ b)$

$\begin{equation}
\left\{
\begin{array}{l}
x_1=-y_0 & \\
x_0-ky_0= y_1
\end{array}
\right.
\end{equation}$

遞迴可解出解出
$\begin{equation}
\left\{
\begin{array}{l}
x_n& \\
y_n
\end{array}
\right.
\end{equation}$

---
## mod 乘法反元素
### 題目敘述
給$a,\ m,\ gcd(a,\ m)=1$
找$x\ 使得\ ax\equiv1\pmod{m}$
### 方法1.
使用$ax+my=gcd(a,b)=1$的方法求得
### 方法2. 歐拉-費馬定理
$x=a^{\phi(m)-1}\ mod\ m$
$\phi(m)=1\sim m\ 跟m互質的數字個數$
#### 計算$\phi(m)$
$[p_1,\ p_2,\ p_3,...,p_n]為m的質因數$
$則\phi(m)=m\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \frac{p_3-1}{p_3}\times...\times \frac{p_n-1}{p_n}$

---
## 中國剩餘定理 CRT
### 題目敘述
求最小的$x$使得
$\begin{equation}
\left\{
\begin{array}{l}
x\equiv a_1\ mod\ m_1 & \\
x\equiv a_2\ mod\ m_2 & \\
x\equiv a_3\ mod\ m_3 & \\
\vdots &\\
x\equiv a_n\ mod\ m_n & \\
\end{array}
\right.
\end{equation}$
### 解法
$令M=m_1\times m_2\times m_3 \times ... \times m_n$
$令M_i=\frac{M}{m_i}$
$令t_i=M_i^{-1}\ mod\ m_i$
$則x=\sum Mi\times t_i\times a_i$

---