notes

Appearance

数学 ​

取余相关 ​

当且仅当 ，其中 是整数。

费马小定理 ​

费马小定理主要作用于对分数进行取模运算。

例如 对 取模，通过费马小定理可将其化为求 的值，在计算过程中为了防止越界，还需用快速幂算法进行优化。

快速幂的代码实现：

cpp
int ksm(int a, int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % M;
        b >>= 1;
        a = a * a % M;
    }
    return res;
}

即对分数的取模运算可直接输出：

cpp
cout << P * ksm(Q, M - 2) % M << endl;

求组合数 ​

预处理+逆元 ​

组合公式:

通过逆元将除法化为乘法：

首先预处理出 和 的值，并通过费马小定理求出 和 的逆元，最后将其相乘即可。

c++代码实现：

cpp
const int M = 1e9 + 7;
const int N = 1e6+5;
ll fac[N], infac[N]; 

void intal() {
    fac[0] = infac[0] = 1;
    for (int i = 1; i <= 1e6 + 1; i ++ ) {
        fac[i] = fac[i - 1] * i % M;
        infac[i] = infac[i - 1] * ksm(i, M - 2) % M;
    }
}

ll C(ll a, ll b)
{
    return fac[a] * infac[a - b] % M * infac[b] % M;
}

适用于 和 在 的范围内。

卢卡斯定理 ​

卢卡斯定理:

C++代码实现：

cpp
int qmi(int a, int k, int p) {
    int res = 1 % p;
    while (k) {
        if (k & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}

// 定义求解
int C(int a, int b, int p) {
    if (b > a) return 0;
    int res = 1;
    for (int i = 1, j = a; i <= b; ++i, --j) {
        res = (ll)res * j % p;
        res = (ll)res * qmi(i, p - 2, p) % p;
    }
    return res;
}

int lucas(ll a, ll b, ll p) {
    if (a < p && b < p) return C(a, b, p);
    // 递归让其到p范围内求解
    return (ll)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

适用于 和 在 的范围内。
其中 为质数。

素数筛 ​

我们事先不知道一个数是否为素数，但是我们可以创造出合数（非素数）。

数字可以划分为素数和合数两大类，那么当我们把某一范围内的合数都标记出来，则剩下的数字就是素数。即从 开始，依次将 的倍数、 的倍数、 的倍数……标记为合数。

c++代码实现(欧拉筛)：

cpp
vector<ll> sieve(ll n)
{
    vector<ll> primes;
    vector<bool> vis(n + 1, 0);
    for (ll i = 2; i <= n; i++) {
        if (vis[i] == 0)
            primes.push_back(i);
        for (ll j = 0; j < primes.size(); j++) {
            if (i * primes[j] > n)
                break;
            vis[i * primes[j]] = 1;
            if (i % primes[j] == 0)
                break;
        }
    }
    return primes;
}

返回值为 以内的所有素数。

常用数学结论及公式 ​

  • 表示按位异或， 表示按位与

  • 对于 ，有

    • 当 时，
    • 当 时， 可以取任意整数
    • 当 时，

  • 中位数定理：给定一个数组，每次操作加1或者减1，将所有元素变成相同的最小操作次数则是将所有元素变成中位数即可。

为 的逆元。
加上 是为了防止负数取模。