质数

线性筛法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e6 + 10;

int n, cnt;
int st[N];

void n_prime(int n) {
    for (int i = 2; i <= n; i ++) {
        if (!st[i]) {
            prime[cnt++] = i;
        }
        for (int j = 0; prime[j] <= n / i; j ++) {
                st[prime[j] * i] = 1;
                if (i % prime[j] == 0) break;
        }
    }
}

int main () {
    cin >> n;
    e_prime(n);
    cout << cnt;
    return 0;
}

埃氏筛法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e6 + 10;

int n, cnt;
int st[N];

void e_prime(int n) {
    for (int i = 2; i <= n; i ++) {
        if (st[i]) continue;
        prime[cnt++] = i;
        for (int j = i + i; j <= n; j += i) st[j] = 1;
    }
}

int main () {
    cin >> n;
    e_prime(n);
    cout << cnt;
    return 0;
}

求组合数

求组合数

首先给出组合数的定义：\(C\_n^m = \frac{\overbrace {n \times (n - 1) \times (n - 2) \times ...\times (n - m + 1)}^\text{m 个 数}}{1 \times 2\times 3\times ... \times m} = \frac{n!}{(n - m)! \times m!} = C\_{n -1}^{m} + C\_{n - 1}^{m - 1} \tag {1}\)

对于 $ 1 $ 号公式，我们可以这样理解：假如我们有 n 个苹果，要从中任意挑选 m 个苹果，我们首先可以拿出来 1 个苹果，那么接下来一共就两种方案：

1. 包含这 1 个苹果的方案 ： 也就是从 n - 1个苹果中挑选 m - 1 个苹果。

\(C\_{n - 1}^{m - 1} \tag {*}\)

2. 不包含这 1 个苹果的方案，也就是从 n - 1 苹果中挑选 m 个苹果。

\(C\_{n - 1}^{m} \tag {**}\)

由以上公式我们就得到如下递推式：
\(C\_n^m = C\_{n -1}^{m} + C\_{n - 1}^{m - 1} \tag {***}\)

递推式计算的时间复杂度是 \(O(n^2)\) 的, 其中 \(n\) 代表 \(max(a, b)\) 。

很像后面动态规划的整数划分那个题目。

此外还有一种 \(O(nlog_n)\) 的计算方法。
需要用到快速幂求逆元跟预处理阶乘。
\(C\_n^m =\frac{n!}{(n - m)! \times m!}\)

逆元又是什么呢？之前基础课讲过，这里简单的再介绍一下。
比如要求一个 \(\frac{a}{b}~ \% ~mod\) ，因为对于除法的取余我们很难计算，因为有时候并不是整除，而且最重要的是

\(\frac{a}{b} ~\%~ mod \neq \frac{a~ \%~ mod}{b ~\%~ mod}\) ，因此我们转换成逆元计算：
设 \(x\) 为 \(b\) 的逆元，那么 \(\frac{a}{b} ~\%~ mod \equiv (a ~\%~ mod) \times (x ~\%~mod) \% ~mod\)

计算逆元的方法：\(X = Quickpower(B, Mod - 2, Mod)\),当且仅当 \(Mod\) 是一个质数的时候成立。

时间复杂度：\(O(n + log_{mod})\)。

\(Lucas~Theory\) 卢卡斯定理 \(O(p \times log\_N \times log\_p)\) ，其中 \(p\) 为模数且必须是质数，\(N\)为\(ab\)的大小.

证明略。

\(C_{a}^{b} \equiv C_{a~mod~p}^{b~mod~p} \times C_{\frac{a}{p}}^{\frac{b}{p}} ~~ (mod~p)\)

\(O(n^2)\) 递推公式求组合数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010, MO = 1e9 + 7;
int c[N][N];

void init () {
    for (int a = 0; a < N; a ++) {
        for (int b= 0; b <= a; b ++) {
            if (b == 0) c[a][b] = 1;
            else c[a][b] = (c[a - 1][b] + c[a - 1][b - 1]) % MO;
        }
    }
}

int main () {
    int n;  
    cin >> n;
    init();
    while (n --) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", c[a][b]);
    }
    return 0;
}

\(O(n~log_{n})\) 逆元做法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 100010, mod = 1000000007;
int fact[N], infact[N];
int n;

int qmid(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) res = (LL) res * a % p;
        a = (LL) a * a % mod;
        b >>= 1;
    }
    return res;
}

int main () {
    cin >> n;
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++) {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmid(i, mod - 2, mod) % mod;
    }
    while (n --) {
        int a, b;
        cin >> a >> b;
        printf("%d\n", (LL)fact[a] * infact[a - b] % mod * infact[b] % mod);
    }
    return 0;
}

\(O(p \times log_N \times log_p)\)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
int p;

int qmid(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (LL) res * a % p;
        a = (LL) a * a % p;
        b >>= 1;
    }
    return res;
}

int C(int a, int b) {
    int res = 1;
    for (int i = a, j = b; j >= 1; j --, i --) {
        res = (LL) res * i % p;
        res = (LL) res * qmid(j, p - 2) % p;
    }
    return res;
}

int locas (LL a, LL b) {
    if (a < p && b < p) return C(a, b) % p;
    return (LL)C(a % p, b % p) * locas(a/p, b/p) % p;
}

int main () {
    int n;
    cin >> n;
    while (n --) {
        LL a, b;
        cin >> a >> b >> p;
        cout << locas(a, b) << endl;
    }
    return 0;
}

y总的代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


const int N = 5010;

int primes[N], cnt;
int sum[N];
bool st[N];


void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


int get(int n, int p){
    int res = 0;
    while (n){
        res += n / p;
        n /= p;
    }
    return res;
}


vector<int> mul(vector<int> a, int b){
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ ){
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t){
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}


int main(){
    int a, b;
    cin >> a >> b;

    get_primes(a);

    for (int i = 0; i < cnt; i ++ ){
        int p = primes[i];
        sum[i] = get(a, p) - get(a - b, p) - get(b, p);
    }

    vector<int> res;
    res.push_back(1);

    for (int i = 0; i < cnt; i ++ )
        for (int j = 0; j < sum[i]; j ++ )
            res = mul(res, primes[i]);

    for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
    puts("");

    return 0;
}

数论（一）