数论是数学的一个分支，研究整数的性质和关系。在C++中，数论算法常用于解决竞赛编程、密码学等问题。以下是一些常见的数论概念及其C++实现。

---

素数判断

素数是指大于1的自然数，除了1和它本身外没有其他因数。

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

---

埃拉托斯特尼筛法

用于快速生成一定范围内的所有素数。

void sieveOfEratosthenes(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) {
                isPrime[j] = false;
            }
        }
    }
    // 打印所有素数
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) cout << i << " ";
    }
}

---

最大公约数（GCD）

使用欧几里得算法计算两个数的最大公约数。

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

C++17及以上版本提供了内置的std::gcd函数。

---

最小公倍数（LCM）

两个数的最小公倍数可以通过它们的最大公约数计算得出。

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

---

模运算

模运算在数论中非常重要，常用于处理大数问题。

• 加法取模
  $(a + b) \mod m = (a \mod m + b \mod m) \mod m$

• 乘法取模
  $(a \times b) \mod m = (a \mod m \times b \mod m) \mod m$

• 快速幂取模
  计算$a^b \mod m$的高效方法。

long long fastPowMod(long long a, long long b, long long m) {
    long long res = 1;
    a = a % m;
    while (b > 0) {
        if (b & 1) res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

---

扩展欧几里得算法

用于求解方程$ax + by = \gcd(a, b)$的整数解$(x, y)$。

int extendedGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int g = extendedGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

---

模逆元

模逆元是指对于整数$a$和模数$m$，找到整数$x$使得$ax \equiv 1 \mod m$。

int modInverse(int a, int m) {
    int x, y;
    int g = extendedGcd(a, m, x, y);
    if (g != 1) return -1; // 逆元不存在
    return (x % m + m) % m; // 确保结果为正值
}

---

中国剩余定理

用于解决一组同余方程：

$x \equiv a_1 \mod m_1$
$x \equiv a_2 \mod m_2$
...
$x \equiv a_n \mod m_n$

int chineseRemainder(vector<int> &a, vector<int> &m) {
    int n = a.size();
    int M = 1;
    for (int i = 0; i < n; ++i) M *= m[i];
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int Mi = M / m[i];
        int inv = modInverse(Mi, m[i]);
        res = (res + a[i] * Mi * inv) % M;
    }
    return res;
}

---

组合数计算

组合数$C(n, k)$表示从$n$个元素中取$k$个的组合数，可以通过动态规划或公式计算。

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

对于大数取模的组合数，通常需要预计算阶乘和逆阶乘。

---

欧拉函数

欧拉函数$\phi(n)$表示小于或等于$n$的正整数中与$n$互质的数的个数。

int eulerPhi(int n) {
    int res = n;
    for (int p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            res -= res / p;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}

---

以上是C++中常见的数论算法实现，涵盖了素数、GCD、模运算、组合数等核心内容。这些算法在竞赛编程和实际应用中非常有用。