數論與組合數學基礎
數論基礎
整除： a整除b 記做a|b
因數與倍數： a|b即a是b的因數，b是a的倍數
帶餘除法： 對于整數a，b（b！=0），設a除以b的商為q，餘數為r，則a=bq+r，q，r為整數且0≤r≤|b|
模： a除以b餘數為r，記為a modb = r
同餘： a，b模p同餘即a，b除以p的餘數相同，記做a≡b（mod p）
類比十進制運算個位數的規律，不難發現：
(amodp±bmodp)modp=(a±b)modp ( a m o d p ± b m o d p ) m o d p = ( a ± b ) m o d p
(amodp)(bmodp)modp=abmodp ( a m o d p ) ( b m o d p ) m o d p = a b m o d p
注意C++的取模和取餘是不一樣的，C++的取模是保留符号
的，如(−4) mod 3 = 2，但C++中(-4)%3=-1
質數：正因數隻包含1和它本身的正整數（2,3,5,7···）
合數：正因數包含除1和它本身外的數的正整數
（4,6,8,9···）
篩質數
1.暴力枚舉
枚舉i=1，2，……，n 判斷i是否包含【2,√i】内的因數（因數集合具有對稱性） 效率太低，考慮改進！！！！
2.一種篩（不知道叫啥）
枚舉正整數a,b ≥ 2且ab ≤ n，将ab标記為合數
3.埃拉托斯特尼篩法（埃氏篩法）：
優化：隻要枚舉a為質數的ab
4.線性篩：
性篩法基本思想：每個數隻被最小的質因子篩一次，即對
于a是質數，b的最小質因子不小于a的整數對a,b，标記ab為合數
實作：先枚舉b，再枚舉a，枚舉到a|b時結束
質數分布定理：π(n) ∼n/lnn ，π(n)為n以内質數個數
是以存放質數的數組可以開小一些
給定正整數n ≤ 10 7 ，求n的質因數分解式
O(n)預處理n以内質數，同時預處理每個合數x的最小質因
子p x
每次分解不斷将n提取一個p x
由于每提取一個質因子n就會減半，單次分解複雜
度O(logn)
最小公倍數與最大公約數
a,b的最大公因數為最大的正整數c，c|a且c|b，記
作c = gcd(a,b)或c = (a,b)，特别地(a,0) = (0,a) = 0
a,b的最小公倍數為最小的正整數c，a|c且b|c，記
作c = lcm(a,b)或c = [a,b]
性質：
(a,b) = (a,b ± a)
(a,b) · [a,b] = ab
給定正整數a 0 ,a 1 ,b 0 ,b 1 ，求有多少個正整數x滿足：
1. x和a 0 的最大公約數是a 1
2．x和b 0 的最小公倍數是b 1
不超過2000組資料，a 0 ,a 1 ,b 0 ,b 1 ≤ 2 × 10 9
原根
常用的數論函數
注意！！！
歐拉函數
容斥原理
莫比烏斯函數
莫比烏斯反演