:+1: [2020 競技程設教材 HackMD Book](https://hackmd.io/@nckuacm/ryLIV6BYI) :+1:

2019 Week 14: Number theory
=

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

# Modular arithmetic (同餘運算)

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

#### 練習：
[CODEFORCES 1165A Remainder](https://codeforces.com/contest/1165/problem/A)

若**數字們**都對 $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](https://codeforces.com/contest/1151/problem/C)
[CODEFORCES 1165E Two Arrays and Sum of Functions](https://codeforces.com/contest/1165/problem/E)[^sort]

## 歐拉定理
如果 $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$，它倆各自有**自己的因數**[^factor]，取**相同**的因數中**最大**的數，即最大公因數 $\gcd(a, b)$

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

#### 練習：

[CODEFORCES 1155C Alarm Clocks Everywhere](https://codeforces.com/contest/1155/problem/C)
[CODEFORCES 1133D Zero Quantity Maximization](https://codeforces.com/contest/1133/problem/D)
[CODECHEF SnackDown 2019 Round 1A Chef and Periodic Sequence](https://www.codechef.com/problems/PERIODIC)
[CODEFORCES 1107D Compression](https://codeforces.com/contest/1107/problem/D)
### 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
> 輾轉相除法

:::info
給定整數 $a, b$ 求出 $\gcd(a, b)$
:::

令 $a_0=a, b_0=b$，根據 [GCD 性質](#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}
$$

#### 練習：
:::warning
證明上述過程 $\gcd$ 中**左**參數比**右**參數要先變為 $0$
:::

 [^euclidean]

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

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

#### 練習：
[UVa OJ 10407 Simple division](https://uva.onlinejudge.org/external/104/10407.pdf)

## Bezout’s Theorem
對於所有整數 $a, b$，存在**整數** $x, y$ 使得 $ax + by = \gcd(a, b)$

## Extended Euclidean algorithm

:::info
給定整數 $a, b$ 求出整數 $x, y$ 滿足 $ax + by = \gcd(a, b)$
:::

令 $g = \gcd(a, b)$，配合 [Bezout’s Thm](#Bezout’s-Theorem) 得到：
$$ 0\cdot x_n + g\cdot y_n = g$$
明顯的，$x_n \in \mathbb{Z}, y_n = 1$
> 即 $x_n$ 為任意整數

而根據 [GCD 性質](#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](https://uva.onlinejudge.org/external/101/10104.pdf)
[UVa OJ 10090 Marbles](https://uva.onlinejudge.org/external/100/10090.pdf)
[UVa OJ 10413 Crazy Savages](https://uva.onlinejudge.org/external/104/10413.pdf)

[^factor]: 整數 $n$ 的**因數**為可**整除** $n$ 的數
[^euclidean]: [Wikipedia/ 輾轉相除法的演示動畫](https://zh.wikipedia.org/zh-tw/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95#/media/File:Euclidean_algorithm_252_105_animation_flipped.gif)
[^sort]: 請留意 mod 後大小關係會改變QQ