數(shù)論

整數(shù)的整除性

1. [x]表示不超過x的最大整數(shù)，叫做取整函數(shù)或高斯函數(shù)。
2. 設(shè)整數(shù)a，b不同時為零，則存在一對整數(shù)m，n，使得$(a,b)=am+bn$。注：a和b的最大公因數(shù)會寫成 (a, b) 的形式，最小公倍數(shù)會寫成 [a, b] 的形式。
3. 若$a|bc$，且$(a,b)=1$，則$a|c$。
4. 設(shè)p為素數(shù)，若 $p|ab$，則 $p|a$，或 $p|b$。推論：設(shè)p為素數(shù)，若 $p|a_1{a}_2...a_k$，則存在$a_i(1\le i\le k)$，使得$p|a_i$。
5. $(a,b)[a,b]=|ab|$.
6. 求多個整數(shù)的最大公因數(shù)，可以這樣轉(zhuǎn)化：(a, b, c) = ((a, b), c)。求多個整數(shù)的最大公倍數(shù)，可以轉(zhuǎn)化為：[a, b, c] = [[a, b], c]。
7. 算術(shù)基本定理：任何大一1的整數(shù)可以分解成素因數(shù)乘積的形式，并且，如果不計分解式中素因數(shù)的次序，這種分解式是惟一的。
8. 一般地，對給定的兩個大于1的整數(shù)a, b,找出它們所有的互異素因數(shù)，然后將a, b表示成這些素因數(shù)的冪的乘積，如果其中一個素因數(shù)在a或b中不出現(xiàn)，就將這個素因數(shù)的冪指數(shù)寫作0，那么(a, b)可以表示成這些素因數(shù)的冪的乘積，每個素因數(shù)的冪指數(shù)為其在a與b中的冪指數(shù)的最小者，而[a, b]也可以表示成這些素因數(shù)冪的乘積，每個素因數(shù)的冪指數(shù)為其在a與b的冪指數(shù)的最大者.

同余

1. $a\equiv b(modn)?n|a?b$.
2. 若 $a\equiv b(modn)$，且$c\equiv d(modn)$，則

• $a+c\equiv b+d(modn)$;
• $ac\equiv bd(modn)$
• $ka\equiv kb(modn)$，k為任意整數(shù)
• $a^m\equiv b^m(modn)$，m為正整數(shù)

3. 若$ab\equiv ac(modn)$，且$(a,n)=1$，則$b\equiv c(modn)$.
4. 我們把所有與整數(shù)a模n同余的整數(shù)構(gòu)成的集合叫做模n的一個剩余類，記作[a]，并把a叫做剩余類[a]的一個代表元。
5. $a\equiv b(modn)?[a]=[b].$
6. 剩余類加法：$[a]+[b]=[a+b]$。剩余類乘法：$[a][b]=[ab]$。
7. [0]叫剩余類環(huán)的零元，[1]叫剩余類環(huán)的單位元。若$[a]+[b]=[b]+[a]=[0]$，則稱[b]為[a]的負元。若$[a][b]=[b][a]=[1]$，則稱[b]為[a]的逆元。
8. 非零元[a]有逆元的充要條件是$(a,n)=1$。n就是剩余類定義里面的那個n。
9. 在模n的剩余類環(huán)中，若[a]存在逆元，則它的逆元僅有一個。
10. 無零因子：任意兩個非零整數(shù)的乘積不等于0。但是，剩余類乘法中并不都滿足這個條件。比如模6的剩余類乘法，$[2][3]=0$。但是模5的剩余類環(huán)無零因子。
11. 設(shè)m為素數(shù)，a為任意整數(shù)，且$(a,m)=1$，則$a^{m?1}\equiv 1(modm)$.
12. 歐拉定理：設(shè) m 為正整數(shù)，a 為任意整數(shù)，且$(a,m)=1$，則：$a^{?(m)}\equiv 1(modn)$，其中$?(m)$表示1，2，3，…，m 中與m互素的正整數(shù)的個數(shù)。若在算數(shù)基本定理中，$N=p_1^{a_1}?p_2^{a_2}?\dots ?p_m^{a_m}$，則：$\phi (N)=N?\frac{p_1?1}{p_1}?\frac{p_2?1}{p_2}?\dots ?\frac{p_m?1}{p_m}$。不過要指出的是，$\phi (1)=1$。
13. 一次同余方程$ax\equiv b(modn)$有解，則$(a,n)|b$。反過來，當$(a,n)|b$，一次同余方程$ax\equiv b(modn)$恰有(a, n)個解。
14. $\frac{b}{a}\%p=b?a^{?1}\%p=b?a^{p?2}\%p$

一次不定方程

1. 二元一次不定方程$ax+by=c$有解，等價于$(a,b)|c$。
2. 設(shè)$(a,b)=1$，則不定方程ax+by=c的整數(shù)通解為$$\{\begin{array}{l}x=x_0+bt\\ y=y_0?at\end{array}$$其中t為任意整數(shù)，$x=x_0,y=y_0$為不定方程$ax+by=c$的一個特解。
3. 三元一次不定方程$ax+by+cz=d$有整數(shù)解的充要條件是$(a,b,c)|d$

原根與指數(shù)

原根

1. 設(shè)(a,m) = 1,則
   (i)存在正整數(shù)n,$1\le r<m$,使$a^n=1$(mod m);
   (ii)設(shè)n為(i)中最小的正整數(shù)，則對整數(shù)k和l,同余式 $a^k=a^l(modm)$ 成立的充分必要條件是$k\equiv l(modn)$.特別地，$a^k=1(modm)$成立的充分必要條件為n|k.
2. 對與m互素的整數(shù)a,滿足$a^n=1(modm)$的最小正整數(shù)n,稱為a模m的階.

組合數(shù)學(xué)

組合數(shù)

• 一個組合數(shù)是否為奇數(shù)：$C(n,k)$為奇數(shù)時，$n\&k=k$ 。
• 令$a_n={\sum }_{x=0}^N{C}_N^x?2^x$：$a_0=1$，$a_n=3?a_{n?1}$。

求和公式

1.平方和公式

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-SemLiPww-1686468029027)(null)]

2.立方和公式

$\sum _{i=1}^n{i}^3=1^3+2^3+...+n^3=\frac{n^2(n+1{)}^2}{4}=[\frac{n(n+1)}{2}{]}^2$

微積分

積分表

• 積分表1：

• 積分表2：

• 積分表3：

$\pi$ 的值

• 不用記住準確值，一行代碼就可以了呀。把這個放在main函數(shù)外面也是沒問題的。

const double PI = acos(-1);

其他

1. 在數(shù)學(xué)中，以Kenneth E. Iverson命名的“艾佛森括號”，是一種用方括號記號，如果方括號內(nèi)的條件滿足則為1，不滿足則為0。
2. 格雷碼規(guī)則：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-NC5Ypxxs-1686468028452)(file:///D:\1398687709\1398687709\Image\C2C\3144C8683FBA94C26F58702AA73A398E.png)]