「取餘數」，也就是 C++ 中的 % 運算子，是一個在程式競賽中很常使用到的運算，除了餘數本身的性質有許多派上用場的時機之外，也有許多題目是因為答案非常大，而要求要先把答案取個餘數後再輸出。「取餘數」這個運算有個名字叫作模運算（modulo），也叫作模或模除，在寫數學式子的時候通常會寫成 $\bmod$，例如 $5 \bmod 2$ 就是取 $5$ 除以 $2$ 的餘數，也就是 $1$，讀作「五模除二」（更多時候會簡稱成「五模二」）或是「$5$ modulo $2$」。
在這個小節中，寫成等寬字體的 a / b 是指 C++ 程式碼之中的整數除法，數學字體 $a / b$ 或 $\frac{a}{b}$ 是指數學上除法的結果，也就是沒有經過取整的有理數。
a % b 就是 a 除以 b 取餘數這件事情聽起來非常簡單，畢竟我們國小就學過怎麼取餘數了，不過這件事情其實沒有表面上這麼單純──如果哪天我們需要對負數進行模運算怎麼辦？$-5 \div 3$ 應該是 $-5 \div 3 = -1 \ldots -2$ 還是 $-5 \div 3 = -2 \ldots 1$？在 C++ 中，a % b 就等同於 a - a / b * b，而在 C++ 裡面的整數除法是「向零取整」，也就是除完的結果不是整數的時候，會取比較靠近 0 的那個整數，所以 -5 / 3 的結果會是 -1、-5 % 3 的結果會是 -5 - (-5) / 3 * 3 == -2，5 / -3 的結果也是 -1，不過 5 % -3 的結果是 5 - 5 / (-3) * (-3) == 2。
不過，在實際的使用上，大多時候我們的模數 $b$ 都是正整數，而且我們其實會比較希望 $a \bmod b$ 是一個非負整數，也就是 $a \bmod b$ 的定義是
$a \bmod b$ 是將 $a$ 表示成 $kb+r$、$k$ 是整數時，最小的可能的非負整數 $r$。在這個時候，$k$ 會是 $\lfloor \frac ab \rfloor$，而 $r$ 肯定是 $[0, \lvert b \rvert)$ 之間的整數。
如果在對一個負數取模的時候，希望獲得非負的餘數，也就是 $a - \lfloor \frac ab \rfloor$ 的話，可以寫成 (a % b + b) % b，這樣就一定會得到 $[0,b)$ 之內的結果了。這麼做的原因是因為 a % b 肯定是一個在 $(-b,b)$ 之內的整數，加上 $b$ 之後肯定會變成 $\geq 0$，最後需要再模 $b$ 一次是因為有可能本來 a % b 的結果就是 $\geq 0$ 了，這樣 $+b$ 之後會 $\geq b$，所以要再模一次。
注意 (a % b + b) % b 這個寫法需要 $b > 0$。
剛剛提到 a / b 會「向零取整」，也就是在 $\frac ab$ 的結果是正時會向下取整（$\lfloor \frac ab \rfloor$）、是負時會向上取整（$\lceil \frac ab \rceil$），那麼要怎麼實作向下取整或向上取整的運算呢？不要使用 <cmath> 提供的 floor 和 ceil 函數，因為它們都是浮點數運算，會有浮點數誤差的問題，正確的作法是：
a / b。a / b 就是 $\lceil \frac ab \rceil$，如果 $\frac ab$ 不整除的話，$\lfloor \frac ab \rfloor=\lceil \frac ab \rceil - 1$，所以答案是 a / b - 1。剛剛我們其實做了一些不太容易理解的事情：把 $a$ 先模 $b$、再加上 $b$、再模 $b$，這樣答案真的跟 $a \bmod b$ 一樣嗎？要暸解為什麼可以這樣，我們先來暸解同餘的概念：
$a \equiv b \pmod m$ 的條件是 $m \mid (a - b)$，也就是 $\frac{a-b}{m}$ 整除。這個式子完整讀作「$a$ 跟 $b$ 在模 $m$ 下同餘」。
再寫一次模運算的定義：$k = \lfloor \frac ab \rfloor$、$r = a \bmod b$ 時，$a = kb+r$，移項一下就變成 $\frac{a - r}{b} = k$，而 $k$ 是一個整數，因此 $a \equiv r \pmod{b}$。很明顯地
\[ a \equiv b \pmod m \iff a \bmod m = b \bmod m \]
也就是模 $m$ 後一樣的數字就同餘。$\equiv$ 這符號跟 $=$ 長得很像，從某種角度來說，可以視為同餘就是「在模運算之下的等於」，它跟等於有多像呢？
對於任意整數 $a,b,c$、正整數 $m$，如果 $a \equiv b \pmod m$，那麼：
這些的證明都很簡單，只要代入同餘的定義即可，讀者可以練習看看。
所以說，$\equiv$ 兩邊的兩個數字一起加減乘一個數字，都不會改變它們同餘的關係，而且還有遞移律，就跟我們平常認識的 $=$ 很像！不過也有一些不一樣的地方，注意到我們只提到「加減乘」，但四則運算中的除法並沒有跟它們一起出現，這是因為把兩邊除上一個數後，不見得會保持同餘關係，先不談不整除的時候不知該怎麼辦，光是整除的狀況就可能會出問題，像是 $6 \equiv 12 \pmod 6$，但是如果把兩邊各自除以 $3$，$2 \equiv 4 \pmod 6$ 顯然是錯的。
有一個真實存在的性質是當 $c$ 是 $a,b,m$ 的公因數時，$\frac{a}{c} \equiv \frac{b}{c} \pmod{\frac{m}{c}}$，但通常改變模數並不是我們想要的，之後的篇章會再處理除法的問題，這裡我們先不討論。
既然同餘類似於某種「等於的關係」，那其實可以更進一步地說：
對於任意整數 $a,b,c,d$、正整數 $m$，如果 $a \equiv b \pmod m$ 且 $c \equiv d \pmod m$，那麼：
回來看看我們剛剛寫過的式子：(a % b + b) % b，雖然 % b 出來的結果可能是負的，但它總是個取餘數的運算，a % b 的結果永遠都會跟 $a$ 在模 $b$ 下同餘。所以：
\[
\begin{align*}
& ((a\ \texttt{%}\ b) + b)\ \texttt{%}\ b \\
\equiv\ & (a\ \texttt{%}\ b) + b & (\texttt{%}\text{ 會保持同餘}) \\
\equiv\ & a\ \texttt{%}\ b & (\texttt{\(b\) 跟 \(0\) 同餘}) \\
\equiv\ & a & (\texttt{%}\text{ 會保持同餘}) \\
& (\text{mod}\ \ b)
\end{align*}
\]
得到結果真的會跟 $a$ 模 $b$ 下同餘，我們又知道運算結果是一個 $[0, b)$ 以內的數，所以這個答案就只能是 $a \bmod b$ 了。
在那種「因為答案很大所以要取模再輸出」的題目中，很有可能光是在運算過程中，數字就會大到 long long int 也存不下，所以算完最後再取模肯定是不行的！舉例來說，我們想要算 $2^{100} \bmod 10^9+7$，雖然答案是個連 int 都存的下的數，但要是我們先算完 $2^{100}$ 再模，那一般的整數型態肯定存不下。
同餘的運算 2 其實也告訴了我們，在加減乘運算之前先把數字模一次，也不會改變運算結果，所以其實可以寫成
const long long MOD = 1'000'000'007;
long long ans = 1;
for (int i = 0; i < 100; i++) {
ans = ans * 2 % MOD;
}
就可以得到正確的 $2^{100} \bmod 10^9 + 7$。在做這種題目的時候，可以每做一次運算就模一次，這樣就不會溢位了。
世人其實對於 $\bmod$ 和其他運算符號的優先順序沒有什麼共識，所以在有各種運算交錯出現時，最好還是加個括號才比較不容易搞混。一般來說，$a \bmod 10^9+7$ 就是 $a \bmod (10^9+7)$ 的意思，因為這個式子單獨出現時不太會搞混所以經常省略括號。
注意在 C++ 中 % 的優先度比 + 高、和 * 跟 / 同級，在寫程式的時候要特別注意加減乘模的優先順序，例如 a + b % MOD 的意思其實是 a + (b % MOD) 而非 (a + b) % MOD。
/ 和 % 這兩個運算比 +-* 慢很多！在運算量很大（如超過 $10^8$）的時候，要是每次加減乘完都模一次，時限又設比較緊的話，就有可能會 TLE。有一些減少模運算次數又不會溢位的小技巧：
if (ans >= m) ans -= m;。if (ans < 0) ans += m;。long long int 範圍，可以放心地最後再模。不過乘法完通常就非模不可了。
剛才我們學會怎麼在不溢位的前提下算出 $2^{100} \bmod 10^9+7$，進階一點，如果我們要算的是 $a^b \bmod m$ 呢？
給你非負整數 $a,b$，求 $a^b \bmod 10^9+7$。特別地，定義 $0^0=1$。
慢慢地把 $a$ 乘 $b$ 次是不行的，那得花上 $O(b)$ 的時間，所以我們得想辦法把指數運算算得更快。在國中的時候，我們有學過指數律：
\[ a^b \times a^c = a^{b+c} \]
前面我們計算 $a^b$ 的方法，就是直接算 $a^{b-1} \times a = a^b$，所以我們會依序算出 $a^1,a^2,\dots,a^b$，不過我們需要知道的只有最後那個 $a^n$ 而已，可不可以少知道一點？一種想法是我們乾脆把 $b$「分一半」，如果 $b$ 是個偶數 $b=2k$，那我們知道 $a^b=(a^k)^2$，只需要知道 $a^k=a^{b/2}$ 就能算出 $a^b$ 了。照著這個邏輯，要是 $b$ 是個二的冪次 $b=2^k$ 那就很快樂，因為我們只需要一直把 $a$ 平方，就會依序得出
\[ a=a^{2^0}, \quad (a^{2^0})^2=a^{2^1}, \quad (a^{2^1})^2 = a^{2^2}, \quad \dots, \quad a^{2^k}=a^b \]
只要花 $O(k)=O(\log b)$ 的時間就能得到 $a^b$ 了！
如果 $b$ 不是二的冪次，就代表我們一直除以 2 的話，總有一天會變成一個奇數，這時我們就不能直接分一半了。解決辦法很簡單，把它變成偶數就好了嘛，在 $b$ 是奇數 $b = 2k+1$ 的時候，就有 $a^b=(a^k)^2 \times a$，其實也只要算 $a^k=a^{(b-1)/2}$ 就好了。這樣一來，我們可以先得到一個遞迴的算法：
\[
a^b = \begin{cases}
(a^{b/2})^2, &\qquad \text{if \(b\) 是偶數} \\
(a^{(b-1)/2})^2 \times a, &\qquad \text{if \(b\) 是奇數}
\end{cases}
\]
每次遞迴時 $b$ 就會少一半，所以時間複雜度就是 $O(\log b)$。仔細想想，其實這個過程就等同於去看 $b$ 的二進位分解：
\[ b = \underbrace{b_{\lfloor \log_2 b \rfloor} \dots b_1b_0}_{\text{寫成二進位}}
= b_{\lfloor \log_2 b \rfloor} \times 2^{\lfloor \log_2 b \rfloor} + \dots + b_1 \times 2^1 + b_0 \times 2^0 \]
舉例來說，
\[
182_{(10)} = 10110110_{(2)} = 2^7 + 2^5 + 2^4 + 2^2 + 2^1
\]
所以
\[
a^{182} = a^{2^7} \times a^{2^5} \times a^{2^4} \times a^{2^2} \times a^{2^1}
\]
右邊的東西就是一堆「$a$ 的二的冪次次方」相乘，剛剛我們就已經知道這要怎麼算了，所以可以輕鬆寫成迴圈版本：
using ll = long long;
const ll MOD = 1'000'000'007;
ll fastpow(ll a, ll b) {
ll ans = 1;
while (b > 0) {
if (b & 1) ans = ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ans;
}在那個 while 迴圈第 $i$ 次執行（從 $0$ 開始數）時，當下的 a 會是 $a^{2^i}$，b 會是 $b$ 少掉最右邊的 $i$ 個 bit，所以 b & 1 是在檢查「$b$ 的第 $i$ 個 bit 是不是 1」，是的話就把答案乘上 $a^{2^i}$。用個簡單的小例子，$b=13=1101_{(2)}$，在每次迴圈開始的時候：
ans $=a^0,$ a $= a^1,$ b $= 13 = 1101_{(2)}$，b & 1 是 1，ans 被更新成 $a^1$。ans $=a^1,$ a $= a^2,$ b $= 6 = 110_{(2)}$，b & 1 是 0，ans 不變。ans $=a^1,$ a $= a^4,$ b $= 3 = 11_{(2)}$，b & 1 是 1，ans 被更新成 $a^5$。ans $=a^5,$ a $= a^8,$ b $= 1 = 1_{(2)}$，b & 1 是 1，ans 被更新成 $a^{13}$。b 變成 0 了，迴圈結束。時間複雜度和遞迴版本同樣是 $O(\log b)$。
不要直接用 <cmath> 裡面的 pow()！那是一個浮點數函數。
國小的時候，老師教我們用短除法計算兩個數 $a,b$ 的最大公因數，作法是先神祕地通靈出一個它們的共同因數 $d$ 之後，把它們都除以 $d$，然後反覆這個動作，直到它們互質為止，過程中所有 $d$ 相乘就是最大公因數了。不過寫程式的時候，我們無法看著數字就猜一個公因數出來，要是像我們在基礎演算法 / 學校教的數學枚舉因數那樣做的話也得要花 $O(\max(\sqrt{a},\sqrt{b}))$ 的時間。
要更快算出最大公因數的話，就要用到輾轉相除法了，輾轉相除法也叫作歐幾里得演算法（Euclidean algorithm），它用到一個最大公因數的性質：
對於任意一個 $a,b$ 的公因數 $d$，令 $a=a'd,b=b'd$，我們有 $b-a=(b'-a')d$，仍是一個 $d$ 的倍數，所以 $d$ 是 $a,b-a$ 的公因數。
對於任意一個 $a,b-a$ 的公因數 $d$，令 $a=a'd, b-a=td$，我們有 $b=(t+a')d$，仍是一個 $d$ 的倍數，所以 $d$ 是 $a,b$ 的公因數。
總的來說，$d$ 是 $a,b$ 的公因數若且唯若 $d$ 是 $a,b-a$ 的公因數。
輾轉相除法的作法很簡單，就是不斷把 $a,b$ 之中大的減去小的，有一個變成 $0$ 之後就直接回傳另一個數字。不過一直慢慢減不見得很快，要是 $a$ 很大、$b=1$，那就要減到天荒地老了，比較聰明的作法是直接令 $a \gets a \bmod b$，畢竟 $a$ 一直扣掉 $b$ 直到變成比 $b$ 還小，那不就是 $a$ 模 $b$ 嗎？
這樣真的很快嗎？分析一下時間複雜度，假設 $a > b$，那事實上 $a \bmod b \leq a/2$，因為要是 $b \leq a/2$ 那自然是對的，如果 $b > a/2$ 的話，那麼 $a \bmod b = a - b < a/2$，所以每一次都有其中一個數會少一半，時間複雜度就是 $O(\log a + \log b)$。
其實在只是要用最大公因數的時候，不需要自己寫輾轉相除法，從 C++17 開始 <numeric> 提供 gcd() function，內部的實作就是用輾轉相除法，開心地用下去就好了。在更低的版本的話，在 <algorithm> 裡面有一個叫作 __gcd() 的 function，不過要注意這個 function 不在標準之中，能用 gcd 還是用 gcd 比較好。
那為什麼要學輾轉相除法呢？不久後就知道了。
檢查一個數 $n$ 是不是質數可以 $O(\sqrt{n})$ 時間內做到，但是如果我們想要找 $1$ 到 $n$ 內的所有質數，花上 $O(n\sqrt{n})$ 的時間一一檢查好像太慢了，這時就要用更聰明的辦法找質數了。
一個直覺的想法是，我們枚舉 $2$ 到 $n$ 的每一個數 $i$，但我們不是要檢查 $i$ 是不是質數，而是去把 $i$ 的兩倍以上倍數都標記成「不是質數」，而沒被標記的那些數就是質數了。
vector<bool> sieve1(int n) { // prime[i] = i 是不是質數
vector<bool> prime(n + 1, true);
prime[0] = prime[1] = false;
for (int i = 2; i <= n; i++)
for (int j = 2 * i; j <= n; j += i)
prime[j] = false;
return prime;
}聽起來好暴力，但這其實很快，被枚舉到的倍數數量會是
\[ \frac{n}{1} + \frac{n}{2} + \dots + \frac{n}{n} = O(n \log n) \]
正整數的倒數和 $\frac{1}{1}+\frac{1}{2}+\dots+\frac{1}{n}$ 叫作調和級數，它的成長率就是 $O(\log n)$，調和級數很常見，在需要枚舉「$1$ 到 $n$ 所有數字在 $n$ 以內的倍數」或是「$1$ 到 $n$ 所有數字的因數」時，要記得總數就只有 $O(n \log n)$ 那麼多。
不過篩質數還可以更快！其實我們剛剛做了一些多餘的事情：要是我們已經知道 $i$ 不是質數了，那代表我們曾經用一個它的因數 $x$ 來把它標記成不是質數，而這個 $x$ 當然也已經去砍掉所有 $i$ 的倍數了，因此不是質數的 $i$ 我們就可以跳過：
vector<bool> sieve2(int n) {
vector<bool> prime(n + 1, true);
prime[0] = prime[1] = false;
for (int i = 2; i <= n; i++)
if (prime[i])
for (int j = 2 * i; j <= n; j += i)
prime[j] = false;
return prime;
}這有比較快嗎？有，質數的倒數和成長率是 $O(\log \log n)$，所以這麼做的時間複雜度只要 $O(n \log \log n)$，幾乎跟線性一樣快了，還可以順便知道每個數的質因數。
一個數 $x$ 會有幾個因數和幾個質因數呢？因為每個質因數都 $\geq 2$，所以 $x$ 的質因數數量是 $O(\log n)$。至於因數數量，如果先找好質因數分解
\[ x = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k} \]
的話，就可以枚舉每個質因數要取幾個，用 $O(\text{因數數量})$ 的時間找到所有因數。在競賽中常見的 $x \leq 10^{9}$ 與 $x \leq 10^{18}$ 範圍中，因數數量最多分別是 $1344$ 與 $103680$，打競賽時通常會直接用 $O(x^{\frac{1}{3}})$ 去算。不過實際上，一個數的因數數量是 $o(x^\epsilon)\ \forall \epsilon > 0$，也就是說，在 $x$ 很大的時候其實是遠少於 $x^{\frac{1}{3}}$ 的。
給兩個整數 $a,b$，求它們的最大公因數。
給你一個 $\geq 2$ 的正整數 $N$，請輸出所有 $[1,N]$ 之間的質數。
可以試試看用 $O(C \log C)$（$C=$ $x$ 的值域大小）的時間做出這題：
給 $n$ 個數 $x$，求每個 $x$ 的因數數量。
請試試用類似於快速冪的作法做出這題，請不要寫大數運算，也不要用如 __int128 等範圍較大的整數型態：
給 $a,b,n$，求 $ab \bmod n$。