注：机试以解题为主，优化其次

判定质数

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

分解质因数

void divide(int x){
    for (int i = 2; i <= x / i; i ++ ){
        if (x % i == 0){
            int s = 0;
            while ( x % i == 0) x /= i, s ++ ;  //相同的质因数计算次数
            cout << i << " " << s << endl;
        }
    }
    if (x > 1) cout << x << " " << 1 << endl;  //剩余大于1的数也为质因数
}

求所有约数

vector<int> get_divisors(int x){
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ ){
        if (x % i == 0){
            res.push_back(i);
            if (i != x / i) res.push_back(x / i); //约数成对出现，相同则不保存
        }
    }
    sort(res.begin(), res.end());
    return res;
}

求最大公约数

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

快速幂

void qmi(int m, int k, int p){
    int res = 1, t = m;
    while (k){
        if (k & 1 == 1) res = res * t % p;
        t = t * t % p;
        k = k >> 1;
    }
    return res;
}

求组合数

c[a][b]表示从a个球中取出b个球的方案数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (j == 0) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;