如果你曾經卡在一道要求給出「對一個大質數取模」後答案的競賽題上，那麼你其實已經與競賽程式設計中的數論正面打過照面了。
數論研究的是整數：整除性、質數、餘數，以及連接它們的那些出人意料的規律。在 美國計算機奧林匹克競賽（USACO） 這類比賽以及眾多線上評測系統中，這些思想反覆出現，常常偽裝在計數問題、幾何或組合數學之中。好消息是，核心工具箱並不大，既學得會又有回報。掌握它能讓學生在更高難度的分組中獲得穩定的優勢。
數論在競賽中為何重要
大多數程式設計競賽要求你計算精確的整數答案，而這些答案可能會膨脹到天文數字。為了讓結果保持在 64 位元整數範圍內，題目常常要求給出答案對一個固定質數（例如 1,000,000,007）取模後的值。僅這一個要求就牽涉出一整套技巧：模加法、模乘法、模冪運算以及模除法。數論同時也是計數的語言，因此組合數學問題非常依賴它。
具體到 USACO，數論往往出現在 Silver 和 Gold 分組中，模運算和最大公因數在那裡成為標準工具。隨著學生向 Platinum 和國際資訊學奧林匹克競賽邁進，這些思想會更加深入，但根基始終不變。這正是我們在 競賽程式設計課程 中把這部分內容作為核心課程的原因。
必備工具箱
你不需要修一門大學課程才能上手。下面這些基礎模組涵蓋了絕大多數競賽場景：
最大公因數（GCD）與歐幾里得演算法
歐幾里得演算法透過不斷用餘數替換較大的數，在大約 O(log min(a, b)) 的時間內求出兩個整數的 GCD。它的「近親」——擴展歐幾里得演算法，則能找到滿足 ax + by = gcd(a, b) 的整數 x 和 y。這一擴展是求解線性方程式和計算模反元素背後的主力。
質數與埃拉托斯特尼篩法
埃拉托斯特尼篩法透過標記每個質數的倍數，在約 O(n log log n)（接近線性）的時間內列出不超過 n 的所有質數。基於這個篩法，你可以建構快速的質因數分解，並預先計算出某個區間內每個數的最小質因數——這一技巧能把許多「給這個數分解因數」的子問題變成瞬間查表。
模運算與快速冪
用餘數進行運算，能讓數字保持較小，同時對加法、減法和乘法保持正確性。要高效計算 a^b mod m，可使用二進位（快速）冪，它透過反覆平方在 O(log b) 內完成。這一個常式出現在極大比例的中高難度題目中。
模反元素與計數
在模運算下，除法是個棘手的操作。當模數為質數 p 時，費馬小定理指出：對於任意不被 p 整除的 a，有 a^(p-1) 同餘於 1（mod p），因此 a 的反元素就是 a^(p-2) mod p。搭配預先計算好的階乘，這能讓你快速計算二項式係數「n 選 r」對質數取模的結果，而這正是無數組合數學任務的支柱。
一個行之有效的學習順序是：先 GCD，再篩法，然後是模運算與快速冪，最後是模反元素與組合數學。每一步都會重用前一步的內容。
值得逐步進階的主題
一旦這些必備內容變得駕輕就熟，下面這些中級思想能進一步拓展你的能力邊界：
- 歐拉函數 φ(n)：統計不超過 n 且與 n 互質的整數個數，是歐拉定理的基礎——歐拉定理把費馬的結論推廣到了非質數模數。
- 中國餘數定理（CRT）：根據一個數對若干兩兩互質的模數所得的餘數來重建這個數，當沒有一個足夠大的質數可用時很有用。
- 線性篩：一種能在線性時間內於某區間上計算積性函數的篩法變體。
數論獎勵善於辨識規律的人。同樣的五六個工具會以新的「裝扮」反覆出現，因此在經典題目上有針對性地刻意練習，勝過死記幾十種邊界情況。
如何高效練習
只有動手實作，理論才能真正記牢。每個演算法至少從零手寫一遍，然後做按難度分級的題集——在把概念混合之前，先逐個隔離地練習單一概念。像 USACO Guide 這樣精選的進階題單會按主題和難度組織題目，我們的 部落格 也會分享更多學習策略。由於競賽形式會不斷演變，請始終以官方競賽網站為準核對當前的賽制、分組和參賽資格，而不要只依賴任何單篇文章。
數論是年輕選手所能做出的回報最高的投資之一：一組精煉的思想就能解鎖橫跨演算法、數學和資訊學的諸多問題。如果你的孩子已準備好在有結構的輔導與回饋中打下這一基礎，歡迎了解我們的 競賽程式設計課程，即刻開始。