数的算法

基本算术

　高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

模运算

快速幂。求
$$

typedef long long LL;
LL qmi(int a, int k, int p) {
    LL ret = 1;
    while (k) {
        if (k & 1) ret = ret * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return ret;
}

素数判定

• 质数(素数)

  定义：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数（素数）。小于等于1的数既不是质数，也不是合数。

试除法

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

分解质因数–试除法

n中最多只包含一个大于n√n的质因子
最好O(logn)，最坏O(√n)

void divide(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            cout << i << ' ' << cnt << endl;
        }
    }
    if (n > 1) cout << n << ' ' << 1 << endl;
}

朴素筛质数

O(nlogn)O(nlog⁡n)

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

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

埃氏筛质数

O(nlog)

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

线性筛质数

O(n)
nn只会被最小的质因子筛掉，每个数只有一个最小质因子，所以每个数只会被筛一次
当pj∣ipj∣i时，pjpj一定是ii的最小质因子，也一定是pj∗ipj∗i的最小质因子
当pj∤ipj∤i时，pjpj一定小于ii的最小质因子，pjpj也一定是pj∗ipj∗i的最小质因子

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;
        }
    }
}

位运算

基本操作

与 & 都为真为真
或 | 有一个为真就为真
非 ! 真的变假，假的变真
异或 ^ 如果相同为0，不同为1

• 未完待续

Hash

• 未完待续。。。