算法中的数论基础

算法中的数论基础

本篇文章适用于算法考试或比赛之前的临场复习记忆，没有复杂公式推理，基本上是知识点以及函数模版，涵盖取模操作、位运算的小技巧、组合数、概率期望、进制转换、最大公约数、最小公倍数、唯一分解定理、素数、快速幂等知识点

一、取模操作

取模也叫取余，设 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⁻¹ 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. 使用场景

• 计算概率问题时（如抽卡问题）。
• 动态规划中的状态转移涉及选择元素（如背包问题）。
• 组合数学问题（如路径计数、多项式展开）。