数学知识

[TOC]

质数：

题目连接

试除法判定质数:

1
2
3
4
5
6
7
8
//试除法判定质数还是很强的，可以判定很大的数是不是质数。
bool IsPrime(int x){
    if(x < 2) return false;
    for(int i = 2; i <= x/i; i++){
        if(x%i == 0) return false;
    }
    return true;
}

试除法分解质因数：

1
2
3
4
5
6
7
8
9
10
11
12
//分解质因数是除以所有可以整除的因子，并累计个数。最后的数如果不是1，就说明是质数
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;
    cout << endl;
}

线性筛：

1
2
3
4
5
6
7
8
9
10
11
12
//vis[x] = 1,说明这个数是合数。prime数组表示n的范围内所有的质数，下标从零开始。
int Prime(int n){
	int cnt = 0;
	for(int i = 2; i < n; i++){
		if(!vis[i]) prime[cnt++] = i;
		for(int j = 0; prime[j] < n/i; j++){
			vis[i*prime[j]] = 1;
			if(i % prime[j] == 0) break;
		}
	}
	return cnt;
}

约数

题目链接

试除法求所有约数：

1
2
3
4
5
6
7
8
9
10
11
12
13
//一次性清除所有的约数
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;
}

最大公约数：

1
2
3
4
//或调用库函数__gcd(a,b)
long long gcd(long long a,long long b){
	return b? a : gcd(b,a % b);
}

最小公倍数：

1
2
3
4
//和gcd的时间复杂度都是logn
long long lcm(long long a,long long b){
	return a/gcd(a,b)*b;
}

约数之和与约数个数：

如果 N = p1^c1 * p2^c2 * … *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * … * (ck + 1)
约数之和： (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)

欧拉函数

试除法求欧拉函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//求单个较大的数的欧拉函数
int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

筛法求欧拉函数：

$$
设p为质数，若p|n,且p^2|n,则\phi(n) = \phi(n/p)*p
$$

$$
设p为质数，若p|n,且p^2!|n,则\phi(n) = \phi(n/p)*(p-1)
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉

//求1-N之间素数的同时求出欧拉函数
void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

拓展欧几里得算法：

$$
裴蜀定理：对于任意整数a,b,存在一对整数，满足ax+by = gcd(a,b)
$$

1
2
3
4
5
6
7
8
9
//求a与b的最大公约数，x与y的值是ax+by = gcd(a,b)的一组特解x0，y0
//对于一般方程ax+by = c，当c是gcd(a,b)的倍数时，方程有整数解。
//令x0，y0同时乘上c/d得到一组特解，通解可以表示为x = c/d*x0+k*b/d,y = c/d*y0-k*a/d(k为任意整数)
int exgcd(int a,int b,int &x,int &y){
    if(b == 0) {x = 1;y = 0;return a;};
    int d = exgcd(b,a%b,y,x);
    y -= a/b*x
    return d;
}

拓展欧几里得算法求线性同余方程：

1
2
3
4
5
6
7
8
9
10
//给定正数a，b，m，求一个整数a*x与b模m同余，或给出无解，我们称之为线性同余方程
while(T--){
        int a,b,m,x,y;
        cin >> a >> b >> m;
        
        int d = exgcd(a,m,x,y);
        
        if(b%d) puts("impossible");
        else cout << (long long)x*(b/d)%m << endl; //模m是为了求得最小整数解
    }

高斯消元（求解线性多元方程组）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// a[N][N]是增广矩阵
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ ) // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}

快速幂：

1
2
3
4
5
6
7
8
9
10
11
12
//指数不断除2，底数不断平方
long long quick_pow(long long base, long long power) {
    long long res = 1;  //此处等价于if(power%2==1)
    while (power) {
        if (power & 1) {
            res = res * base % MOD;
        }
        power >>= 1;
        base = (base * base) % MOD;
    }
    return res;
}

求组合数:

核心公式：
$$
C_a^b = \frac{a!}{b!*(a-b)!}
$$

递归法求组合数：
1
2
3
4
5
6
7
8
9
10
11
//用递推的方式求组合数，适用于a和b较小的情况下，时间复杂度是n^2
//选定一堆苹果中的一个苹果，分不选或选这个苹果两种情况讨论
void init(){
    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;
        }
    }
}

通过预处理逆元的方式求组合数：
1
2
3
4
5
6
7
8
9
10
11
12
//预处理每一个数的阶乘和每一个数阶乘的逆元，直接代入公式计算
//时间复杂度NlogN，适用于a和b在1e5的范围
void init(){
    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i++){
        fact[i] = fact[i-1]*i % MOD;
        infact[i] = infact[i-1]*quick_pow(i,MOD-2)%MOD;
    }
}

//输出
cout << fact[a]*infact[b]%MOD*infact[a-b]%MOD << endl;
Lucas定理求组合数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//若p是质数，则对于任意整数m,n，有： C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
//时间复杂度O(logpN*p*logp),对于n较大时，通常用这种方法
ll C(ll a,ll b){
    ll res = 1;
    for(int i = 1,j = a; i <= b; i++,j--){
        res = res * j % p;
        res = res * quick_pow(i,p-2)%p;
    }
    return res;
}

ll lucas(ll a,ll b){
    if(a < p && b < p) return C(a,b);
    else return C(a%p,b%p)*lucas(a/p,b/p)%p;
}
卡特兰数:

给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//只求一个组合数可以直接求，时间复杂度为logN*N
int main(){
    int n;
    cin >> n;
    
    int a = 2*n,b = n;
    
    ll res = 1;
    for(int i = 1,j = a; i <= b; i++,j--){
        res = res * j % MOD;
        res = res * quick_pow(i,MOD-2)%MOD;
    }
    
    cout << res*quick_pow(n+1,MOD-2)%MOD << endl;
}