算法中的數論基礎

本篇文章適用于算法考試或比賽之前的臨場復習記憶，沒有復雜公式推理，基本上是知識點以及函數模版，涵蓋取模操作、位運算的小技巧、組合數、概率期望、進制轉換、最大公約數、最小公倍數、唯一分解定理、素數、快速冪等知識點

一、取模操作

取模也叫取余，設 a,b 為兩個給定的整數，a≠0。設 dd 是一個給定的整數。那么，一定存在唯一的一對整數 qq 和 rr，滿足 b=qa+r,r<b。也就是我們很就學過的除法取余。

在編程語言中，我們常用 % 符號代表取模。

在比賽題目中，當結果非常大時，通常要求取模運算，取模有如下性質：

• (a % M + b % M) % M = (a + b) % M
• (a % M) * (b % M) % M = (a * b) % M

所以在編程比賽中，為了防止整數溢出，基本每進行一次運算就要一次取模，因此常常會看到：

(a * b % M + c) % M * d % M

注意：取模僅對加法和乘法滿足上述性質，但是對除法不滿足

二、位運算的小技巧

1.基礎位運算

包括：<< >> ~ & | ^ 這些運算符的使用方法

2.給一個數n，確定它的二進制表示中的第x位是0還是一

if((n >> x) & 1)	return 1;
else return 0;

3.將一個數的二進制表示中的第x位修改為0或1

//修改為0
n = n & (~(1 << x))
//修改為1
n = n | (1 << x)

4.位圖的思想

將一個變量的每一個二進制位看成一個標志位，這就像STM32中的寄存器一樣，每一位存放不同的數代表不同的狀態

5.提取一個數(n)二進制中最右邊的1

n & (-n);

示例：

 0110101000//n1001010111//n的反碼1001011000//加1之后的補碼
&01101010000000001000

6.干掉一個數(n)二進制表示中最右側的1

n & (n - 1);

7.位運算的優先級

對于位運算的優先級，能用括號就用括號

9，異或運算

//1. a ^ 0 = a;
//2. a ^ a = 0;
//3. a ^ b ^ c = a ^ (b ^ c);

• a + b == 2 * (a & b) + (a ^ b)`：同學們可以嘗試證明一下。
• Lowbit(x) == x & (-x)：獲取整數 xx 的最低位。
• a ^ b <= a + b ：可通過位的異或性質具體證明。

三、組合數

組合數的思想

組合數C(n,k)表示從n個元素中選取k個元素的方案數，其核心在于無重復、無順序的選擇。這種思想常用于需要枚舉所有可能組合或計算組合數量的場景。

如何應用組合數

1. 直接計算組合數：

   • 公式法：利用階乘直接計算，但需注意溢出，適用于小規模數據。

     int combination(int n, int k) 
     {if (k > n) return 0;if (k == 0 || k == n) return 1;return combination(n - 1, k - 1) + combination(n - 1, k);
     }
     

   • 動態規劃預處理：適用于多次查詢，結合模運算避免溢出。

     const int MOD = 1e9 + 7;
     vector<int> fact, inv;// 計算 (a^b) % mod，使用快速冪算法
     int pow_mod(int a, int b, int mod) 
     {int ret = 1;a %= mod;  										// 確保 a 在 mod 范圍內while (b > 0) {if (b % 2 == 1)   							// 如果當前二進制位為1，乘上對應的冪ret = (ret * 1LL * a) % mod;  			// 注意用 1LL 避免溢出a = (a * 1LL * a) % mod;  					// 平方并取模b /= 2;  									// 移動到下一個二進制位}return ret;
     }// 預處理階乘和逆元
     void precompute(int max_n) 
     {fact.resize(max_n + 1);inv.resize(max_n + 1);fact[0] = 1;for (int i = 1; i <= max_n; ++i)fact[i] = (1LL * fact[i - 1] * i) % MOD;inv[max_n] = pow_mod(fact[max_n], MOD - 2, MOD); // 快速冪求逆元for (int i = max_n - 1; i >= 0; --i)inv[i] = (1LL * inv[i + 1] * (i + 1)) % MOD;
     }
     int C(int n, int k) 
     {if (k < 0 || k > n) return 0;return (1LL * fact[n] * inv[k] % MOD) * inv[n - k] % MOD;
     }
     

     注意：

     1. (1LL * fact[n] * inv[k] % MOD) * inv[n - k] % MOD;

2. 生成所有組合：

   • 回溯法：通過遞歸生成所有可能的組合。

     #include <vector>
     using namespace std;void dfs(int s, int n, int k, vector<int>& path, vector<vector<int>>& ret) 
     {if (path.size() == k) {ret.push_back(path);return;}// 提前剪枝：剩余元素不足以填滿組合時提前終止for (int i = s; i <= n - (k - path.size()) + 1; ++i) {path.push_back(i);dfs(i + 1, n, k, path, ret);path.pop_back();}
     }vector<vector<int>> combine(int n, int k) 
     {vector<vector<int>> ret;vector<int> path;dfs(1, n, k, path, ret);return ret;
     }
     

注意事項

• 溢出問題：當n較大時，直接計算階乘會導致溢出，需使用模運算和預處理。
• 效率考量：生成所有組合的時間復雜度為O(C(n,k))，應避免在n較大時使用。
• 剪枝優化：在回溯過程中及時剪枝（如剩余元素不足時終止遞歸），提升效率。

四、概率論與期望集定義式

C++中的實現方法

1. 直接計算期望（小規模問題）

• 場景：狀態數少且概率明確的問題（如簡單骰子問題）。

• 示例代碼：

  double calculateDiceExpectation() {double expectation = 0.0;for (int i = 1; i <= 6; ++i) {expectation += i * (1.0 / 6.0);}return expectation; // 輸出3.5
  }
  

2. 動態規劃（中等規模問題）

• 場景：狀態轉移具有概率依賴的問題（如隨機游走、迷宮逃脫）。

• 示例問題：
  一個迷宮中有陷阱（概率( p )死亡）和出口（概率( 1-p )逃脫），求逃脫的期望步數。

• 遞推公式：
  [
  E[i] = 1 + p \cdot E[\text{死亡}] + (1-p) \cdot E[\text{逃脫}]
  ]
  簡化后：
  [
  E[i] = \frac{1}{1-p} \quad (\text{若死亡則期望為無窮大})
  ]

• 代碼實現：

  double mazeEscapeExpectation(double p) {if (p >= 1.0) return INFINITY; // 必死情況return 1.0 / (1.0 - p);
  }
  

注意事項與優化技巧

1. 浮點數精度問題
   • 使用double類型時，避免連續乘除導致精度損失。

• 對精度敏感的問題可改用分數形式（如分子分母分開存儲）。

2. 狀態壓縮與記憶化

   • 當狀態參數較多時，用位運算或哈希表壓縮狀態。
   • 示例：

    unordered_map<State, double> memo;double dp(State s) {if (memo.count(s)) return memo[s];// 計算邏輯return memo[s] = result;}

五、進制轉換

C++中進制轉換詳解（二進制、十進制、十六進制互轉）

一、核心方法總結

轉換方向	標準庫方法	手動實現法	應用場景
十進制 → 其他	cout格式控制符、bitset	除基取余法	輸出格式化、算法題快速實現
其他 → 十進制	stoi()/stol()指定基數	按權展開計算	輸入解析、自定義轉換邏輯
二 ? 十六	通過十進制中轉或二進制分組轉換	四位二進制對應一位十六進制	數據壓縮、內存地址處理

二、具體實現方法

1. 十進制 → 二進制

方法1：使用 bitset（固定位數）

#include <bitset>
int num = 42;
cout << "二進制: " << bitset<8>(num) << endl; // 輸出00101010

方法2：遞歸除基取余法（動態位數）

string decimalToBinary(int n) {if (n == 0) return "0";string bin;while (n > 0) {bin = to_string(n % 2) + bin;n /= 2;}return bin;
}
// 調用示例：cout << decimalToBinary(42); // 輸出101010

2. 十進制 → 十六進制

方法1：使用 cout 格式控制符

int num = 255;
cout << "十六進制（小寫）: " << hex << num << endl;    // 輸出ff
cout << "十六進制（大寫）: " << uppercase << hex << num; // 輸出FF

方法2：手動轉換（支持負數）

string decimalToHex(int num) {if (num == 0) return "0";const char hexDigits[] = "0123456789ABCDEF";string hex;unsigned int n = num; // 處理負數轉為補碼while (n > 0) {hex = hexDigits[n % 16] + hex;n /= 16;}return hex;
}
// 調用示例：cout << decimalToHex(-42); // 輸出FFFFFFD6

3. 二進制 → 十進制

方法1：使用 stoi 函數

string binStr = "101010";
int decimal = stoi(binStr, nullptr, 2); // 第二個參數為終止位置指針
cout << decimal; // 輸出42

方法2：按權展開計算

int binaryToDecimal(string binStr) {int dec = 0;for (char c : binStr) {dec = dec * 2 + (c - '0');}return dec;
}
// 調用示例：cout << binaryToDecimal("101010"); // 輸出42

4. 十六進制 → 十進制

方法1：使用 stoi 函數

string hexStr = "FF";
int decimal = stoi(hexStr, nullptr, 16); // 第三個參數指定基數
cout << decimal; // 輸出255

方法2：手動轉換（支持大小寫）

int hexCharToValue(char c) {if (isdigit(c)) return c - '0';c = toupper(c);return 10 + (c - 'A');
}int hexToDecimal(string hexStr) {int dec = 0;for (char c : hexStr) {dec = dec * 16 + hexCharToValue(c);}return dec;
}
// 調用示例：cout << hexToDecimal("1a"); // 輸出26

5. 二進制 ? 十六進制（直接轉換）

核心思路：每4位二進制對應1位十六進制

string binaryToHex(string binStr) {// 補齊到4的倍數位（左側補0）binStr = string((4 - binStr.size() % 4) % 4, '0') + binStr;const string hexDigits = "0123456789ABCDEF";string hex;for (size_t i = 0; i < binStr.size(); i += 4) {string chunk = binStr.substr(i, 4);int value = bitset<4>(chunk).to_ulong();hex += hexDigits[value];}// 去除前導0（保留最后一個0）hex.erase(0, hex.find_first_not_of('0'));return hex.empty() ? "0" : hex;
}// 調用示例：binaryToHex("101010") → "2A"

三、應用場景與注意事項

1. 算法題常見應用

   • 位運算優化：二進制轉換常用于位掩碼操作（如狀態壓縮）
   • 內存地址處理：十六進制用于表示內存地址（如0x7ffeeb0a7c）
   • 文件格式解析：如解析PNG文件的IHDR塊中的寬度/高度（十六進制）

2. 關鍵注意事項

   • 溢出處理：使用stol或stoull處理大數（如stoull("FFFF", nullptr, 16)）
   • 輸入驗證：檢查非法字符（如二進制字符串中出現非0/1字符）

   bool isValidBinary(string s) {return s.find_first_not_of("01") == string::npos;
   }
   

   • 負數處理：手動實現時需考慮補碼形式（如bitset<32>(-42).to_string()）

3. 性能優化技巧

   • 預處理映射表：提前建立二進制到十六進制的映射表

   unordered_map<string, char> binToHexMap = {{"0000", '0'}, {"0001", '1'}, /* ... */ {"1111", 'F'}
   };
   

   • 位運算加速：用移位代替除法（如num >>= 1代替num /= 2）

六、最大公約數，最小公倍數，唯一分解定理

最大公約數（GCD）

使用歐幾里得算法（輾轉相除法），支持處理負數和零：

#include <cstdlib>  // 用于abs函數int gcd(int a, int b) 
{a = abs(a);b = abs(b);while (b != 0) {int tmp = a % b;a = b;b = tmp;}return a;
}

最小公倍數（LCM）

基于GCD計算，處理溢出和零的情況：

long long lcm(int a, int b) 
{a = abs(a);b = abs(b);if (a == 0 || b == 0) return 0;  // 0與任何數的LCM為0return (a / gcd(a, b)) * (long long)b;  // 防止溢出
}

唯一分解定理（質因數分解）

高效分解整數為質因數乘積，處理負數和特殊值：

#include <vector>
using namespace std;vector<pair<int, int>> prime_factors(int n) {vector<pair<int, int>> factors;if (n == 0) return factors;  // 0無法分解if (n < 0) {factors.emplace_back(-1, 1);  // 處理負號n = -n;}// 處理因子2if (n % 2 == 0) {int cnt = 0;while (n % 2 == 0) {n /= 2;cnt++;}factors.emplace_back(2, cnt);}// 處理奇數因子for (int i = 3; i * i <= n; i += 2) {if (n % i == 0) {int cnt = 0;while (n % i == 0) {n /= i;cnt++;}factors.emplace_back(i, cnt);}}// 處理剩余的大質數if (n > 1) factors.emplace_back(n, 1);return factors;
}

七、素數

質數（Prime number，又稱素數），指在大于1的自然數中，除了1和該數自身外，無法被其他自然數整除的數（也可定義為只有1與該數本身兩個正因數的數）

素數判斷方法

1. 試除法（Trial Division）

原理：檢查從2到√n的所有整數是否能整除n。
實現代碼：

bool isPrime(int n) 
{if (n <= 1) return false;      // 0和1非素數if (n <= 3) return true;       // 2和3是素數if (n % 2 == 0) return false;  // 排除偶數// 只需檢查奇數因子到√nfor (int i = 3; i * i <= n; i += 2)   if (n % i == 0) return false;  return true;
}

素數篩法

1. 埃拉托斯特尼篩法（Sieve of Eratosthenes）

原理：標記素數的倍數，逐步篩選出所有素數。
實現代碼：

vector<bool> sieve(int n) 
{vector<bool> isPrime(n+1, true);isPrime[0] = isPrime[1] = false;for (int i = 2; i*i <= n; ++i) {if (isPrime[i]) {for (int j = i*i; j <= n; j += i) // 標記i的倍數（從i*i開始）isPrime[j] = false;}}return isPrime;
}

優點：實現簡單，適合大規模區間篩素數。

---

2. 歐拉篩法（線性篩法）

原理：每個合數僅被其最小質因數標記，保證線性時間復雜度。
實現代碼：

vector<bool> eulerSieve(int n) {vector<bool> isPrime(n+1, true);vector<int> primes;  // 存儲素數isPrime[0] = isPrime[1] = false;for (int i = 2; i <= n; ++i) {if (isPrime[i]) primes.push_back(i);// 用當前數和已知素數標記合數for (int p : primes) {if (i * p > n) break;isPrime[i * p] = false;if (i % p == 0) break;  // 保證只被最小質因數標記}}return isPrime;
}

時間復雜度：( O(n) )，空間復雜度 ( O(n) )。

優點：效率更高，適合需要極高性能的場景。

邊界條件：注意處理 ( n = 0, 1 ) 等特殊情況。

八、快速冪，費馬小定理求逆元

快速冪

概念：快速冪是一種高效計算冪運算的算法，將時間復雜度從O(n)降低到O(log n)。其核心思想是通過二分法將指數分解為二進制形式，并利用冪的平方性質減少乘法次數。

實現步驟：

1. 初始化結果為1。
2. 循環處理指數，當指數大于0時：
   • 若當前指數為奇數，將結果乘以底數并取模。
   • 底數平方并取模，指數右移一位（除以2）。

C++代碼示例：

long long fast_pow(long long a, long long b, long long mod) {long long res = 1;a %= mod; // 確保a在mod范圍內while (b > 0) {if (b & 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res;
}

費馬小定理求逆元

概念：當模數p為質數且a與p互質時，a的逆元（即a?1 mod p）可通過費馬小定理計算為a^(p-2) mod p。

使用條件：

• 模數p必須是質數。
• a與p互質（即a不是p的倍數）。

實現方法：直接調用快速冪計算a^(p-2) mod p。

C++代碼示例：

long long mod_inverse(long long a, long long p) {return fast_pow(a, p-2, p);
}

注意事項

• 模數非質數：使用擴展歐幾里得算法求逆元。
• 溢出問題：確保中間結果不超過數據類型范圍，必要時使用快速乘。
• 輸入驗證：確保a與p互質，避免求逆元失敗。

通過結合快速冪和費馬小定理，可以在模數為質數時高效處理涉及除法的模運算問題。

九、排列組合，第二類斯特林數

一、排列組合

1. 概念

• 排列（Permutation）：從 n 個元素中選出 k 個元素 有序排列 的方案數，公式為：
• 組合（Combination）：從 n 個元素中選出 k 個元素 不考慮順序 的方案數，公式為：

2. 實現方法

在模數 MOD（通常為質數如 1e9+7）下，通過預處理階乘和階乘的逆元，實現快速計算：

const int MOD = 1e9+7;
const int MAX_N = 1e5;
long long fact[MAX_N+1], inv_fact[MAX_N+1];// 預處理階乘和逆元階乘
void precompute() {fact[0] = 1;for (int i = 1; i <= MAX_N; i++) {fact[i] = fact[i-1] * i % MOD;}inv_fact[MAX_N] = fast_pow(fact[MAX_N], MOD-2, MOD); // 費馬小定理求逆元for (int i = MAX_N-1; i >= 0; i--) {inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;}
}// 計算排列 P(n, k)
long long permutation(int n, int k) {if (k > n) return 0;return fact[n] * inv_fact[n-k] % MOD;
}// 計算組合 C(n, k)
long long combination(int n, int k) {if (k > n) return 0;return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

二、第二類斯特林數（Stirling Numbers of the Second Kind）

1. 概念

• 定義：將 n 個不同的元素劃分為 k 個 非空集合 的方案數，記為 S(n, k)。
• 遞推公式：
  

2. 實現方法

通過動態規劃遞推計算：

const int MAX_N = 1000;
long long stirling[MAX_N+1][MAX_N+1];void precompute_stirling() {stirling[0][0] = 1;for (int n = 1; n <= MAX_N; n++) {for (int k = 1; k <= n; k++) {stirling[n][k] = (stirling[n-1][k-1] + k * stirling[n-1][k]) % MOD;}}
}) return 0;return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

3. 使用場景

• 計算概率問題時（如抽卡問題）。
• 動態規劃中的狀態轉移涉及選擇元素（如背包問題）。
• 組合數學問題（如路徑計數、多項式展開）。