2019 Week 14: Number theory

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

Modular arithmetic (同餘運算)

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

練習：

CODEFORCES 1165A Remainder

若數字們都對 \(n\) 取餘數後，它們就處於"同餘 \(n\)"的狀態下了
將 \(a\) 除以 \(n\) 的餘數記做 \(a \space (\text{mod } n)\)

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

若 \(a \space (\text{mod } n)\) 與 \(b \space (\text{mod } n)\) 相等，則記 \(a \equiv b \space (\text{mod } n)\)

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

並且若
\[a \equiv b \mod n \\c \equiv d \mod n\]
則
\[a+c \equiv b+d \mod n\\a\times c \equiv b\times d \mod n\]

練習：

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

歐拉定理

如果 \(a, n\) 互質，那麼
\[a^{\phi(n)} \equiv 1 \mod n\]
這裡 \(\phi(n)\) 是與 \(n\) 互質且小於 \(n\) 的正整數的個數

例如 \(1, 5\) 和 \(6\) 互質， \(\phi(6) = 2\)

費馬小定理

如果 \(a, p\) 互質，且 \(p\) 為質數，那麼
\[a^{p-1} \equiv 1 \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 \% a)\)

\(\%\) 是 C++ 中的取餘數運算，表示存在 \(k\) 滿足 \(0 \leq b\% a = b - k\cdot a < a\)

Euclidean algorithm

輾轉相除法

令 \(a_0=a, b_0=b\)，根據 GCD 性質：
\[ \begin{split} \gcd(a_0, b_0) &= \gcd(b_0 \% a_0 = \underline{b_1}, a_0) \\ \gcd(\underline{b_1}, a_0) &= \gcd(a_0 \% b_1 = \underline{a_1}, b_1) \\ \gcd(\underline{a_1}, b_1) &= \gcd(b_1 \% a_1 = b_2, a_1) \\ &\vdots \\ \gcd(a_i, b_i) &= \gcd(b_i \% a_i = a_{i+1}, b_i) \\ &\vdots \\ \gcd(\mathbf{0}, b_n) &= |b_n| \end{split} \]

練習：

^[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

令 \(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\%a_i, a_i)\)
以及 \(b_i \% a_i = b_i - \lfloor{b_i\over a_i}\rfloor \cdot a_i\)
得到
\[ \begin{split} g &= x_j\cdot (b_i \% a_i) &+ y_j &\cdot a_i \\ &= x_j\cdot (b_i - \lfloor{b_i\over a_i}\rfloor \cdot a_i) &+ y_j &\cdot a_i \\ &= x_j \cdot b_i &+ (y_j - \lfloor{b_i\over a_i}\rfloor \cdot x_j) &\cdot a_i \end{split} \]

也就是說
\[ g = a_i \cdot x_{j-1} + b_i \cdot y_{j-1} \text{ for }\begin{cases} x_{j-1} = y_j - \lfloor{b_i\over a_i}\rfloor \cdot x_j \\ y_{j-1} = x_j \end{cases} \]

綜合上述過程：

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