2020 競技程設教材 HackMD Book

2019 Week 14: Number theory

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

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)$

可將括號內看作數字們處於一個特定狀態下，而同餘通常會省略括號

並且若

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

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

練習：

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

歐拉定理

如果

$a,n$ 互質，那麼

$$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$$

是歐拉定理的特例

Greatest Common Divisor

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

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

$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$

^[3]

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

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)$

Extended Euclidean algorithm

給定整數

$a,b$ 求出整數

$x,y$ 滿足

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

令

$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}{rlrl}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

---

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

2. 整數

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

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