数学基础算法模板

1 ~ n所有数的约数个数和 ≈ nlogn
int范围内约数最多的一个数的约数个数 ≈ 1600
如果 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^)

试除法判断质数

时间复杂度O(n^0.5^)

1
2
3
4
5
6
7
8
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;
}

欧拉筛求质数

时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//p:存质数  cnt:质数的个数  st[i]:i是否为质数
int p[N], cnt;
bool st[N];

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

分解质因数

普通分解质因数

时间复杂度O(n^0.5^)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//分解为算术基本定理的形式
void divi(int x)
{
    for (int i = 2; i <= x / i; i ++ )
    {
        if (x % i == 0)
        {
            int cnt = 0;
            while (x % i == 0)
            {
                x /= i;
                cnt ++ ;
            }
            // i质数 cnt质数的指数
            printf("%d %d\n", i, cnt);
        }
    }
    if (x > 1) printf("%d 1\n", x);
}

阶乘分解质因数

时间复杂度约为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//分解为算术基本定理的形式
int p[N], cnt;
bool st[N];
long long n;

//return 算术基本定理分解n!底数p的指数
int get(int n, int p)
{
    int res = 0;
    for (int i = n; i; i /= p) res += i / p;  //核心:先加上n!中p¹的个数, 再加p²......
    return res;
}

for (int i = 0; i < cnt; i ++ )
{
    int ans = get(n, p[i]);
    if (ans) printf("%d %d\n", p[i], ans);
}

最大公约数gcd

时间复杂度约为O(logn)

1
2
3
4
int gcd(int a, int b)
{
    return !b ? a : gcd(b, a % b);
}

试除法求约数

时间复杂度为O(n^0.5^)

1
2
3
4
5
6
7
8
9
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);
    }
}

约数个数

时间复杂度为O(n^0.5^)
如果 N = p1^c1^ * p2^c2^ * … *pk^ck^ (算术基本定理)
约数个数： (c1 + 1) * (c2 + 1) * … * (ck + 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a;
unordered_map<int, int> mp;

for (int i = 2; i <= a / i; i ++ )
{
    while (a % i == 0)
    {
        mp[i] ++ ;
        a /= i;
    }
}
if (a > 1) mp[a] ++ ;

//求a的约数个数
long long res = 1;
for (auto t:mp) res = res * (t.second + 1) % MOD;

约数之和

时间复杂度为O(n^0.5^)
如果 N = p1^c1^ * p2^c2^ * … *pk^ck^ (算术基本定理)
约数之和： (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
15
16
17
18
19
20
21
int a;
unordered_map<int, int> mp;

for (int i = 2; i <= a / i; i ++ )
{
    while (a % i == 0)
    {
        a /= i;
        mp[i] ++ ;
    }
}
if (a > 1) mp[a] ++ ;


LL res = 1;
for (auto t:mp)
{
    LL tmp = 1;
    while (t.second -- ) tmp = tmp * t.first + 1;
    res = res * tmp % MOD;
}

龟速乘

时间复杂度为O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//实现64位整数乘法不溢出
//求a * b % p
typedef long long LL;
LL qmu(LL a, LL b, LL p)
{
    LL res = 0;
    while (b)
    {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}

快速幂

时间复杂度为O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long LL;
LL qmi(LL a, LL b, LL p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}

矩阵乘法

时间复杂度为O(n*m*k)

1
2
3
4
5
6
7
8
9
10
int t[N][N];

void mul(int a[N][N], int b[N][N])
{
    memset(t, 0, sizeof t);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= k; j ++ )
            for (int u = 1; u <= m; u ++ )
                t[i][j] += a[i][u] * b[u][j];
}