信息奧賽中的數學方法第1頁/共75頁目錄基礎數論模意義下的運算費馬小定理、歐拉定理與乘法逆元快速冪與快速乘法輾轉相除法與高精度GCD線性同余方程與拓展歐幾里得算法篩法與質因數分解組合數學入門排列與組合常用公式簡單的組合數取模常用數列容斥原理與禁位排列位運算及bitset第2頁/共75頁基礎數論Basic

Number

Theory第3頁/共75頁基本概念帶余除法模數、取模同余因子互質最大公因數第4頁/共75頁模意義下的運算很多題目的基礎加減乘法在模意義下封閉除法則不同第5頁/共75頁費馬小定理

第6頁/共75頁歐拉定理

第7頁/共75頁乘法逆元

第8頁/共75頁一些大質數

第9頁/共75頁快速冪

第10頁/共75頁快速冪

第11頁/共75頁快速冪：代碼第12頁/共75頁快速乘法

第13頁/共75頁最大公因數（GCD）

第14頁/共75頁更相減損術

第15頁/共75頁輾轉相除法

第16頁/共75頁輾轉相除法：代碼第17頁/共75頁高精度加減乘法

第18頁/共75頁高精度除法

第19頁/共75頁高精度GCD

第20頁/共75頁線性同余方程

第21頁/共75頁拓展歐幾里得算法

第22頁/共75頁拓展歐幾里得算法

第23頁/共75頁拓展歐幾里得算法

第24頁/共75頁拓展歐幾里得算法：代碼第25頁/共75頁求解線性同余方程

第26頁/共75頁分解質因數

第27頁/共75頁枚舉因子

第28頁/共75頁篩法

第29頁/共75頁篩法

第30頁/共75頁基礎數論：

例題BasicNumberTheory:Examples第31頁/共75頁NOIP2012

D2T1

同余方程題面

題解拓展歐幾里得的直接應用。也可以直接算逆元。第32頁/共75頁POJ1061

青蛙的約會題面

題解

第33頁/共75頁HDU2824

TheEulerFunction題意

題解

第34頁/共75頁POJ2480

Longge`sProblem題意

題解

第35頁/共75頁SGU106

TheEquation題意

題解

第36頁/共75頁進一步了解……

第37頁/共75頁組合數學入門Introductory

Combinatorics第38頁/共75頁基本計數原理加法原理乘法原理減法原理第39頁/共75頁計數問題統計滿足某些條件的物體的個數。例：求項鏈的本質不同的染色方案數求圖的不同生成樹的個數答案通常很大，需要取模輸出。兩個要點：不重、不漏第40頁/共75頁排列與組合

第41頁/共75頁Pascal公式

第42頁/共75頁常用公式

第43頁/共75頁常用公式

第44頁/共75頁常用公式

第45頁/共75頁證明的兩種方式組合學推理數學推導第46頁/共75頁嘗試一下證明

第47頁/共75頁模意義下的組合數

第48頁/共75頁Catalan數列

第49頁/共75頁Catalan數列

第50頁/共75頁Bell數列

第51頁/共75頁容斥原理

第52頁/共75頁錯位排列

第53頁/共75頁禁位排列

第54頁/共75頁組合數學入門：例題Introductory

Combinatorics:Examples第55頁/共75頁一道數學題題面

題解

第56頁/共75頁POJ3421

X-factorChains題意

題解

第57頁/共75頁URAL1860

Fiborial題面

題解

第58頁/共75頁POJ3088

PushButtonLock題面

題解

第59頁/共75頁無名試題1題面

題解

第60頁/共75頁《組合數學》習題8.5題面

題解

第61頁/共75頁SKI題面

題解

第62頁/共75頁進一步了解……

第63頁/共75頁位運算與bitsetBitwiseOperationsandstd::bitset第64頁/共75頁位運算第65頁/共75頁集合的二進制表示適用于全集大小比較小（通常在32以內）的情況。用一個unsigned

int表示一個子集。二進制位為1代表子集中有這個元素，0代表沒有。第66頁/共75頁判斷元素是否存在：加入元素：刪除元素：改變元素狀態：

（如果存在則刪除，否則加入）與其他集合的交并異或集合的補：與其他集合的差：集合操作第67頁/共75頁枚舉子集第68頁/共75頁std::bitset

第69頁/共75頁std::bitset用例第70頁/共75頁自己實現bitset內部為unsigned

int數組。與或非異或：對所有數字進行位運算左移右移：第71頁/共75頁自己實現bitset

第72頁/共75頁bitset的簡單應用狀態