5.7 数学

这里介绍程序可能涉及的基础数学计算，算法进阶请学习「数论」，不在本篇范围内。

5.7.1 素数筛法

一个经典的例题，判定质数，其代码如下：

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i<=x/i; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

时间复杂度：#card=math&code=O%28%5Csqrt%20n%29&id=HAHji)

例题：力扣 204. 计数质数

我们现在需要获知连续区间内每一个数是否为质数，如果枚举并判断，时间复杂度为 #card=math&code=O%28n%20%5Csqrt%20n%29&id=PVDwT)。

通过素数筛法，我们可以获得布尔数组，将要判定的数作为下标，取得的数组元素布尔值，即为该下标是否为质数的判断结果。下面提供「埃拉托斯特尼筛法」（简称埃氏筛）的 bitset 优化模板代码（来源： OI Wiki）：

素数筛模板

bitset<N> is_prime;
void Prime(int n) {
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i << 1; j <= n; j += i)
                is_prime[j] = 0;
        }
    }
}

时间复杂度：#card=math&code=O%28n%5Clog%20%5Clog%20n%29&id=EgKH3)。

其中，bitset<N> 可看做是位优化的 bool[N]， 为最大长度。

利用上述模板可以得到素数表，遍历一次可统计出答案。

参考代码

class Solution {
public:
    int countPrimes(int n) {
        const int N = 5e6 + 4;
        bitset<N> is_prime;
        int ans = 0;
        is_prime.set();
        is_prime[0] = is_prime[1] = 0;
        for (int i = 2; i*i <= n; i++) {
            if (is_prime[i]) {
                for (int j = i << 1; j <= n; j += i)
                    is_prime[j] = 0;
            }
        }
        for (int i=2; i<n; ++i) {
            ans += is_prime[i];
        }
        return ans;
    }
};

这套代码在力扣评测系统下，需要频繁开辟大数组，表现一般。它更适合传统竞赛 OJ 的环境。需要指出的是，「线性筛」在以上的大数据量下，速度比埃氏筛几乎快一倍，但其理解难度也更高，此处暂不做展开。

练习：牛客 220829. 素数个数

题目难度不大，请使用筛法完成，之后再阅读下文题解。

题解：

此题有一个小坑，那就是 并非输入，这一反常规状况，写代码越熟练可能越容易忽视，至少让我难受了一下，所以我只能把 干脆写成常量。

统计时使用了一个前缀和，避免每次再累加，这一常规操作，你是否想到了呢。

你可能注意到，在 OJ 判题中，你并非必须一口气读入所有数据，可以和其他预处理交错着写，这使得我们在回答询问时，实际上手中已经有一份已经处理好的答案表了。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1004;
bitset<N> is_prime;
int ans[N];
int n = 1000;
void Prime(int n) {
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i << 1; j <= n; j += i)
                is_prime[j] = 0;
        }
    }
}
int t;
int main() {
    Prime(n);
    for (int i=2; i<=n; ++i) {
        ans[i] = ans[i - 1] + is_prime[i];
    }
    cin >> t;
    while (t--) {
        int k;
        cin >> k;
        cout << ans[k] << endl;
    }
    return 0;
}

5.7.2 分解质因数

按顺序分解的因数，一定都是质数。

#include <bits/stdc++.h>
using namespace std;
int n;
void solve(int x) {
    // O(sqrt(n)): 最多有一个大于 sqrt(x) 的质因数
    for (int i=2; i<=x/i; ++i) {
        if (x % i == 0) {
            int cnt = 0;
            while (x % i == 0) {
                x /= i;
                ++cnt;
            }
            cout << i << ' ' << cnt << endl;
        }
    }
    // 如果存在这个大质因数
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}
int main() {
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        solve(x);
    }
    return 0;
}

时间复杂度：#card=math&code=O%28%5Csqrt%20n%29&id=oZG51)

5.7.3 快速幂 *

实现 C++ 默认 pow(x, y) 的快速计算。这一算法在其他数学方法中时常被调用。

// Quick Pow
#include <iostream>
using namespace std;
typedef long long ll;
ll qpow(ll a, ll b) {   // a ** b
    ll ret = 1;
    while (b) {
        if (b & 1) {
            ret = ret * a;
        }
        a = a * a;
        b >>= 1;
    }
    return ret;
}
// @Overload 需要取模的情况
ll qpow(ll a, ll b, ll m) {   // a ** b % m
    a %= m;
    ll ret = 1;
    while (b) {
        if (b & 1) {
            ret = ret * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return ret;
}
int main() {
    cout << qpow(4, 10) << endl;
    return 0;
}

时间复杂度：#card=math&code=O%28%5Clog%20n%29&id=g0hwH)

参考：快速幂

5.7.4 最大公约数

最大公约数（Greatest Common Divisor，简称 GCD）。

库函数：

__gcd(x, y);

双下划线开头函数为 GNU 环境特别提供，比较方便，但前后数据类型必须一致。更稳妥的做法是，使用欧几里得算法：

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

这一写法建议熟记。

5.7.5 组合数

用 表示从 个物品中选出 个的不同方案数量。

根据数据范围，计算组合数的算法有很多。这里提供一个常规的写法，能适应一般用到组合数计算的问题。

typedef long long ll;
ll res[67][67];
// 该方法能保证在 n = 67, m = 33时才开始溢出 
ll C(ll n,ll m) {
    if (m == 0 || m == n) return 1;
    if (res[n][m] != 0) return res[n][m];    
    return res[n][m] = C(n - 1,m) + C(n - 1,m - 1);    
}

5.7.6 容斥原理

应用于计算各个集合比较方便，但需要集合间运算时。

容斥原理：选中奇数次的集合部分做加法，选中偶数次则做减法。

推荐阅读：数论之容斥原理 与经典例题