数论算法实战：8大核心技巧与C++代码模板

1. 数论基础与算法实战指南

作为算法竞赛和程序设计的基础，数论知识的重要性不言而喻。无论是蓝桥杯等编程竞赛，还是日常的算法优化，掌握这些核心概念都能让你事半功倍。本文将深入解析8个关键数论知识点，并提供可直接套用的C++代码模板。

1.1 位运算的妙用

位运算因其极高的执行效率，在算法优化中扮演着重要角色。让我们从最基础的二进制操作开始：

二进制末位提取技巧

cpp复制int main() {
    int n = 9;  // 二进制表示为1001
    cout << n << "的二进制位(从低位到高位): ";
    while(n > 0) {
        int a = n & 1;  // 取最后一位
        cout << a << " ";
        n >>= 1;  // 右移一位
    }
    // 输出：1 0 0 1 
    return 0;    
}

注意：使用ios::sync_with_stdio(false)和cin.tie(nullptr)可以显著提升C++的I/O速度，在处理大量数据时特别有用。

位操作进阶技巧

1. 奇偶判断：n & 1比n % 2效率更高
2. 特定位操作：

cpp复制// 获取num的第k位（0起始）
int getBit(int num, int k) {
    return (num >> k) & 1;
}

// 设置num的第k位为1
int setBit(int num, int k) {
    return num | (1 << k);
}

1.2 质数处理的艺术

质数相关算法是数论的基础，下面介绍两种常用方法：

埃拉托斯特尼筛法（埃氏筛）

cpp复制const int N = 1e7;
vector<int> prime;
bool is_prime[N];

void Era(int n) {
    fill(is_prime, is_prime+n+1, true);
    for(int i = 2; i <= n; ++i) {
        if(is_prime[i]) {
            p