♠ use C++11 倍數 若 $a,b,k \in \mathbb N$，且 $a \times k=b$，那麼 $b$ 是 $a$ 的倍數，稱 $a$ 整除 $b$，記作 $a \mid b$。 $[1,n]\in \mathbb N$ 中 $x \in \mathbb N$ 的倍數有 $\l ...
♠ use C++11
倍數
-
若 \(a,b,k \in \mathbb N\)，且 \(a \times k=b\)，那麼 \(b\) 是 \(a\) 的倍數，稱 \(a\) 整除 \(b\)，記作 \(a \mid b\)。
-
\([1,n]\in \mathbb N\) 中 \(x \in \mathbb N\) 的倍數有 \(\left \lfloor \dfrac{n}{x} \right \rfloor\) 個。
約數
-
若 \(a \mid b\)，\(a,b\in\mathbb N\)，那麼 \(a\) 是 \(b\) 的約數。
-
\(a \in \mathbb N\) 的約數個數是有限的，記作 \(\operatorname d(n)\)，\(\in \mathbb Z\)。
-
快速算一個序列的 \(\operatorname d(n)\)：設一個計數數組對應每個數，初始為 0，從左到右計算每個數，對於每個倍數加 1，當整個序列計算完後，計數數組的值是其對應數字的約數個數，時間複雜度 \(\mathcal{O}(n\operatorname{log}n)\)。下麵是一個例子：
n 1 2 3 4 5 6
d(n) 0 0 0 0 0 0 start
+1 +1 +1 +1 +1 +1 step 1 in number 1
0 +1 0 +1 0 +1 step 2 in number 2
0 0 +1 0 0 +1 step 3 in number 3
.....and more
1 2 2 3 2 4 end
素數
-
1 不是素數也不是合數。
-
下麵是一串判斷 \(n\in \mathbb N\) 是否是素數的代碼，時間複雜度 \(\mathcal{O}(\sqrt n)\)。
bool is_prime(long long n){
if(n==1) return false;
for(long long i=1;i<=n/i;++i){
if(x%i==0) return false;
}
return true;
}
- 計算一個序列每個數是否是素數：朴素篩法，有較多重覆判斷，時間複雜度 \(\mathcal{O}(n\operatorname{log}n)\)；埃式篩法，僅是素數才向後篩，優化朴素篩法，時間複雜度 \(\mathcal{O}(n\operatorname{log log}n)\)，接近線性篩。
最大公約數
-
若 \(a,b\in \mathbb N\) 且 \(k \mid a,b \in \mathbb N\)，且不存在更大的 \(k\)，稱 \(k\) 是 \(a,b\) 的最大公約數。
-
快速求 \(a,b\in \mathbb N\) 的最大公約數，歐幾裡得定理：\(\gcd(a,b)=\gcd(b,a \bmod b)\)。
-
已知 \(a,b \in \mathbb N\)，可找到 \(x,y \in \mathbb Z\) 使 \(ax +by=\gcd(a,b)\)，若 \(ax+by=1\) 有解，則 \(a\) 和 \(b\) 互質。
-
擴展歐幾裡得，一定存在 \(x,y\in \mathbb N\) 使貝祖等式 \(ax +by=\gcd(a,b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times b + a \bmod b) x + by = \gcd(b,a\bmod b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times x + y) b +(a \bmod b)x\)，可得新的方程 \(b \times x'+(a \bmod b)\times y' = \gcd(b,a\bmod b)\) 因此可得 \(\begin{cases}x'=(\left \lfloor a \div b \right \rfloor\times x+y)\\y'=x\end{cases}\)，同樣倒推可得特解 \(\begin{cases}x=y'\\y=x'-(\left \lfloor a \div b \right \rfloor\times y')\end{cases}\)，下麵是遞歸代碼實現：
array<int,3> exgcd(int a,int b){
if(b==0){
return {1,0,a};
//當b=0時，等式為ax=gcd(a,0)，即ax=a
//得x=1,y=0
}
array<int,3> ans=exgcd(b,a%b);
int temp=ans[0];
ans[0]=ans[1];
ans[1]=temp-a/b*ans[1];
return ans;//ans[0]為x，ans[1]為y，ans[2]為gcd(a,b)
}
- 當求得貝祖等式特解 \(x_0,y_0\in \mathbb N\) 後，可得 \(x,y\in \mathbb N\) 通解，設 \(g=\gcd(a,b)\) 通解為 \(\begin{cases}x=x_0+t\times b\div g\\y = y_0- t \times a \div g\end{cases}\)，推導過程：\(\begin{cases}ax+by=g\\ax_0+bx_0=g\end{cases}\)\(\Rightarrow (x-x_0)a+(y-y_0)b=0\)\(\Rightarrow (x-x_0)a=(y_0-y)b\)\(\Rightarrow (x-x_0)\dfrac{a}{g}=(y_0-y)\dfrac{b}{g}\)\(\Rightarrow \begin{cases}x-x_0=t\times \dfrac{b}{g}\\y_0-y=t \times \dfrac{a}{g}\end{cases}\)\(\Rightarrow \begin{cases} x=x_0+t\times\dfrac{b}{g}\\y=y_0-t\times\dfrac{a}{g}\end{cases}\)，其中 \(x\) 的第一個解是 \(\bigg(x\bmod\dfrac{b}{g}+\dfrac{b}{g}\bigg)\bmod \dfrac{b}{g}\)。
模運算
-
已知 \(a,b,p\in \mathbb N\)，\((a+b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)，\((a-b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)，\((a\times b)\bmod p=(a \bmod p\times b\bmod p)\bmod p\)。
-
若需要進行除法的模運算，與普通的不同，例子：\(\dfrac{20}{10}\bmod 5=2\)\(\nRightarrow\dfrac{20 \bmod 10}{10\bmod 10}\bmod 5=0\)，所以為了求 \((a\div b) \bmod p\)，\(a,b,p\in\mathbb N\)，需要找到 \(b\) 的乘法逆元 \(x\in\mathbb N\)，將算式變成 \((a\times x)\bmod p\)。
-
已知 \(a,x,m\in \mathbb N\)，\(ax \equiv 1\pmod p\)\(\Rightarrow ax \bmod p=1\)\(\Rightarrow ax-\left\lfloor\dfrac{ax}{p}\right\rfloor\times p=1\)，稱 \(x\) 是關於 \(a\) 的乘法逆元，將 \(-\left\lfloor\dfrac{ax}{p}\right\rfloor\) 用 \(y\) 替代，得 \(ax+py=1\),即找到 \(x\) 的值即可找到 \(a\) 的乘法逆元，也可知 \(a,p\) 必須要互質。
