數論内容

1.互素:兩個數的最大公因數是1,則兩數互素,0不在考慮範圍内,1與任何數互素,(不包括0);

2.質因數:每個合數都可以寫成幾個質數相乘的形式，這幾個質數就都叫做這個合數的質因數

3.歐拉函數:

注,從網上搜了很多,發現都是很麻煩的.自己從書上的證明copy下來..感覺這樣證明會很簡單.與大家分享一下..

建議先看一下容斥定理,比較簡單的一個定理.

概念：不超過N的正整數中，與N互質的數的個數。記為F（n）；

公式：F（n） = n*（1-1/p1）*(1-1/p2)```(1-1/pm),其中Pi表示n的質因數,比如12=2^2*3那麼p1=2,p2=3;

證明如下:(根據容斥原理)

設Ai={x/x<=n&&x|pi};即用Ai表示一個在n範圍内的可以整除n的某個質因數的集合.

則F(n) = n-| (A1||A2||A3||````Am) |即為不超過n的總個數n減去與其不互質的個數.

 根據容斥定理:| (A1||A2||A3||```Am) | = sum(Ai)-sum(Ai&&Aj)+````(-1)^x*(sum(Ai&Aj&Ak```)

而|Ai|=[n/pi]=n/pi(因為能夠整除)，|Ai&&Aj| = n/(pi*pj),以此類推.

那麼F(n) = n-sum(Ai)+sum(Ai&&Aj)``````= n - sum(n/pi)+sum(n/(pi*pj))````=n*(1-1/p1)*(1-1/p2)````

最後這一個等号證明還沒弄懂，自己化了下.是這樣的結構(1-a)*(1-b)*(1-c) = 1-a-b-c+ab+ac+bc-abc;剛好是容斥定理的形式..

------------

4.catalen數：

給定一串2n個數的數列,其中含有n個1和n個-1,那麼對于任意子序列Sk來說,滿足Sk>=0,則這個數列滿足catalen數.

公式An = C(2n n)/(n+1);

證明:首先易知符合規則的和不符合規則的數列的總數和應該是從2n個數中選n個作為1的組合.即C(2n n),對于不合規則的數列來說的話,必然存在一個最小的子序列滿足前2K項和為0,同時2K+1項為-1.将前2K+1項全部取反.後面不變,則可以變成一個含有n+1個1和n-1個-1的數列..對于每個不合格的數列都可以變成這樣的一個含有n+1個1和n-1個-1的數列.是以不合格的數列的數目應該是C(2n n+1)..這樣結果An就是C(2n n) - C(2n n+1);