2020 競技程設教材 HackMD Book

2020 Week 14: Number theory

在演算法競賽中，通常涉及的數論大部份是整數的代數性質

Greatest Common Divisor

中譯 最大公因數，以下簡稱 GCD
給定整數

$a,b$，它倆各自有自己的因數^[1]，取相同的因數中最大的數，即最大公因數

$gcd(a,b)$

#include<algorithm> 有內建的 __gcd 函數

練習：

CODEFORCES 1155C Alarm Clocks Everywhere
CODEFORCES 1133D Zero Quantity Maximization
CODECHEF SnackDown 2019 Round 1A Chef and Periodic Sequence
CODEFORCES 1107D Compression

GCD 性質

• $gcd(a,b)=gcd(b,a)$
• $gcd(a,0)=|a|$
• $gcd(a,b)=gcd(a,b\mathrm{\%}a)$

$\mathrm{\%}$ 是 C++ 中的取餘數運算，表示存在

$k$ 滿足

$0\le b\mathrm{\%}a=b-k\cdot a<a$

Euclidean algorithm

輾轉相除法

給定整數

$a,b$ 求出

$gcd(a,b)$

令

$a_0=a,b_0=b$，根據 GCD 性質：

$$\begin{array}{rl}gcd(a_0,b_0)& =gcd(b_0\mathrm{\%}{a}_0=\underset{―}{b_1},a_0)\\ gcd(\underset{―}{b_1},a_0)& =gcd(a_0\mathrm{\%}{b}_1=\underset{―}{a_1},b_1)\\ gcd(\underset{―}{a_1},b_1)& =gcd(b_1\mathrm{\%}{a}_1=b_2,a_1)\\ & ⋮\\ gcd(a_i,b_i)& =gcd(b_i\mathrm{\%}{a}_i=a_{i+1},b_i)\\ & ⋮\\ gcd(\mathbf{0},b_n)& =|b_n|\end{array}$$

練習：

證明上述過程

$gcd$ 中左參數比右參數要先變為

$0$

^[2]

綜合上面過程，實作程式碼：

int gcd(int a, int b)
  { return a? gcd(b%a, a) : b; }

練習：

UVa OJ 10407 Simple division

Bezout’s Theorem

對於所有整數

$a,b$，存在整數

$x,y$ 使得

$ax+by=gcd(a,b)$

練習：

LeetCode 365 Water and Jug Problem

Extended Euclidean algorithm

給定整數

$a,b$ 求出整數

$x,y$ 滿足

$ax+by=gcd(a,b)$

令

$g=gcd(0,g)=gcd(a,b)$，配合 Bezout’s Thm 得到：

$$0\cdot x_n+g\cdot y_n=g$$
明顯的，

$x_n\in \mathbb{Z},y_n=1$

即

$x_n$ 為任意整數

而根據 GCD 性質

$gcd(a_i,b_i)=gcd(b_i\mathrm{\%}{a}_i,a_i)$
以及

$b_i\mathrm{\%}{a}_i=b_i-\lfloor \frac{b_i}{a_i}\rfloor \cdot a_i$
得到

$$\begin{array}{rlr}g& =x_j\cdot (b_i\mathrm{\%}{a}_i)& +y_j\cdot a_i\\ & =x_j\cdot (b_i-\lfloor \frac{b_i}{a_i}\rfloor \cdot a_i)& +y_j\cdot a_i\\ & =x_j\cdot b_i& +(y_j-\lfloor \frac{b_i}{a_i}\rfloor \cdot x_j)\cdot a_i\end{array}$$

也就是說

$$g=a_i\cdot x_{j-1}+b_i\cdot y_{j-1}\text{ for }\{\begin{array}{l}{x}_{j-1}=y_j-\lfloor \frac{b_i}{a_i}\rfloor \cdot x_j\\ y_{j-1}=x_j\end{array}$$

綜合上述過程：

int gcd(int a, int b, int &x, int &y) {
  if(!a) {
    x = 0, y = 1; // x 為任意整數
    return b;
  }

  int g = gcd(b%a, a, x, y);
  int xp = y - b/a * x, yp = x; // p := previous
  x = xp, y = yp;

  return g;
}

練習：

UVa OJ 10104 Euclid Problem
UVa OJ 10090 Marbles
UVa OJ 10413 Crazy Savages

Modular arithmetic (同餘運算)

在競賽中若計算結果超出了數值範圍外，則通常會要求結果對某個數字取餘數
所以得熟悉取完餘數後的數字們之間的關係及運算。

練習：

CODEFORCES 1165A Remainder

若數字們都對

$n$ 取餘數後，它們就處於"模

$n$"的狀態下了
將

$a$ 除以

$n$ 的餘數記做

$a(\text{mod }n)$

記得檢查若 a 為負數的情況

若

$a(\text{mod }n)$ 與

$b(\text{mod }n)$ 相等，則記

$a\equiv b(\text{mod }n)$，稱

$a,b$ 有同餘關係
也就是說

$\mathrm{\forall }k\in \mathbb{Z}\cdot a\equiv a+k\cdot n(\text{mod }n)$

可將括號內看作數字們處於一個特定狀態下，而模

$n$ 通常會省略括號

並且若

$$\begin{array}{c}a\equiv b\mathrm{mod}n\\ c\equiv d\mathrm{mod}n\end{array}$$
則

$$\begin{array}{c}a+c\equiv b+d\mathrm{mod}n\\ a\times c\equiv b\times d\mathrm{mod}n\end{array}$$

練習：

CODEFORCES 1178C Tiles
CODEFORCES 1151C Problem for Nazar
CODEFORCES 1165E Two Arrays and Sum of Functions^[3]

歐拉定理

如果

$a,n$ 互質^[4]，那麼

$$a^{\varphi (n)}\equiv 1\mathrm{mod}n$$
這裡

$\varphi (n)$ 是與

$n$ 互質且小於

$n$ 的正整數的個數

例如

$1,5$ 和

$6$ 互質，

$\varphi (6)=2$

費馬小定理

如果

$a,p$ 互質，且

$p$ 為質數，那麼

$$a^{p-1}\equiv 1\mathrm{mod}p$$

是歐拉定理的特例

模反元素

數字們模

$n$ 後，對於加法、減法、乘法，其性質都與以往差不多，但對數字做除法卻不盡人意

注意，在同餘運算中只會有整數，有理數無理數等其他數不會出現

反元素指的是元素與其運算後為單位元素的元素
例如：

• 整數
  $a$ 的加法反元素為
  $-a$
• 整數
  $a$ 的乘法反元素為
  $\frac{1}{a}$

而元素

$a$ 的模

$n$ 反元素為

$a^{-1}$ 滿足

$$a\cdot a^{-1}\equiv 1\mathrm{mod}n$$

根據 Bezout's Thm

• $ax+ny=gcd(a,n)=1$ 在模
  $n$ 有
  $ax\equiv 1\mathrm{mod}n$
• $ax+ny=gcd(a,n)\ne 1$ 在模
  $n$ 有
  $ax\not\equiv 1\mathrm{mod}n$

也就是說

$gcd(a,n)=1$ (互質)，

$a$ 才擁有模

$n$ 反元素

求出模

$n$ 反元素

• 當
  $n$ 為質數時：

根據費馬小定理有

$$a\cdot a^{n-2}\equiv 1\mathrm{mod}n$$
所以

$a^{n-2}$ 是

$a$ 的模反元素

下週教的快速求冪演算法能在

$O({\log }_{2}n)$ 得到

$a^{n-2}$

• 當
  $n$ 非質數時：

根據 Bezout's Thm 有

$$\begin{array}{rl}& a\cdot x+n\cdot y=1\\ \Rightarrow & a\cdot x\equiv 1\mathrm{mod}n\end{array}$$
可用擴展歐幾里得演算法找到

$x=a^{-1}$

練習：

ZERO JUDGE a289 Modular Multiplicative Inverse
CODEFORCES 300C Beautiful Numbers
NCKU OJ 22 爬樓梯 k
CODEFORCES 935D Fafa and Ancient Alphabet

孫子定理

給定

$a_1,a_2,\cdots ,a_n$ 以及

$m_1,m_2,\cdots ,m_n$ ，其中任意

$m_i,m_j$ 有

$gcd(m_i,m_j)=1$

求滿足下式的

$x$ 值為何？

$$\begin{array}{c}x\equiv a_1\mathrm{mod}{m}_1\\ x\equiv a_2\mathrm{mod}{m}_2\\ ⋮\\ x\equiv a_n\mathrm{mod}{m}_n\end{array}$$

$x$ 要與

$a_i$ 都有關係，所以設

$x=a_1\cdot y_1+a_2\cdot y_2+\cdots +a_n\cdot y_n$，且在模

$m_i$ 時為

$$x=a_1\cdot 0+\cdots +a_i\cdot 1+\cdots +a_n\cdot 0\mathrm{mod}{m}_i$$

要仔細思考，怎樣的

$y_i$ 才會符合問題中的方程式定義？

從小規模觀察，假設

$n=2$，

$x$ 要在

• 模
  $m_1$ 的時候
  $(y_1,y_2)\equiv (1,0)$
• 模
  $m_2$ 的時候
  $(y_1,y_2)\equiv (0,1)$

所以模數應當是對應的

$y_i$ 因數，即

$y_1=m_2\cdot t_1$ 且

$y_2=m_1\cdot t_2$，這樣

• 模
  $m_2$ 的時候
  $y_1\equiv 0$
• 模
  $m_1$ 的時候
  $y_2\equiv 0$

接著思考

$y_1\equiv 1$ 與

$y_2\equiv 1$ 的狀況

• $y_1=m_2\cdot t_1\equiv 1\mathrm{mod}{m}_1$，可推出
  $t_1$ 是
  $m_2$ 的模
  $m_1$ 反元素
• $y_2=m_1\cdot t_2\equiv 1\mathrm{mod}{m}_2$，可推出
  $t_2$ 是
  $m_1$ 的模
  $m_2$ 反元素

最後整理上述有

$$x=(m_2\cdot t_1)a_1+(m_1\cdot t_2)a_2+k\cdot m_1\cdot m_2$$
其中

$k$ 為任意整數

加法最後項

$k\cdot m_1\cdot m_2$ 表示

$x$ 有多種解，是根據同餘關係有

$a\equiv a+k\cdot m\mathrm{mod}m$

根據上述的提示，可以嘗試推廣當

$n>2$ 時

$x$ 的解
如法泡製的將

$m_i$ 作為對應的

$y_j$ 因數，即

$\mathrm{\forall }j\ne i\cdot y_j\equiv 0\mathrm{mod}{m}_i$
所以定義

$M_i=\frac{\prod _{k=1}^n{m}_k}{m_i}$^[5]，該

$y_i$ 可推廣為

$y_i=M_i\cdot t_i$，且

$t_i$ 為

$M_i$ 的模

$m_i$ 反元素

於是推出原問題方程組的解為

$$\begin{array}{rl}x& =(M_1\cdot t_1)a_1+(M_2\cdot t_2)a_2+\cdots +(M_n\cdot t_n)a_n+k\cdot M\\ & =\sum _{k=1}^n(M_i\cdot t_i)a_i+k\cdot M\end{array}$$
其中

$k$ 為任意整數，且

$M=\prod _{k=1}^n{m}_k$

練習：

ZERO JUDGE d791 00756 - Biorhythms
CODEFORCES 687B Remainders Game
Kattis generalchineseremainder Chinese Remainder Theorem (non-relatively prime moduli)
TIOJ 1459 B.完全子圖

---

1. 整數

   $n$ 的因數為可整除
   $n$ 的數 ↩︎

2. Wikipedia/ 輾轉相除法的演示動畫 ↩︎

3. 請留意 mod 後大小關係會改變QQ ↩︎

4. 最大公因數為

   $1$ ↩︎

5. $\prod$ 是連乘符號，也就是說
   $\prod _{k=1}^n{m}_k=m_1\times m_2\times \cdots \times m_n$ ↩︎