数论#

欧拉筛(经典版本) 欧拉筛(最下质数筛) 质因子分解(O(n)筛法,O(logn)质因子分解 ) 矩阵的转置 (横向变纵向，纵向变横向)

欧拉筛(经典版本)#

1
vector<int> pri;
2
void pri_init(int n)
3
{
4
    vector<bool> is_pri(n + 1, true);
5
    is_pri[0] = is_pri[1] = false;
6
    for (int i = 2; i <= n; i++)
7
    {
8
        if (is_pri[i]) pri.push_back(i);
9
        for (int j = 0; j < pri.size() && pri[j] <= n / i; j++)
10
        {
11
            is_pri[pri[j] * i] = false;
12
            if (i % pri[j] == 0) break;
13
        }
14
    }
15
}

欧拉筛(最小质数筛)#

1
vector<int> pri;
2
int pmin[N];
3
void my_pmin(int n)
4
{
5
    for (int i = 2; i <= n; i++)
6
    {
7
        if (pmin[i]==0)
8
        {
9
            pmin[i] = i;
10
            pri.push_back(i);
11
        }
12
        for (auto p : pri)
13
        {
14
            if (i * p > n) break;
15
            pmin[i * p] = p;
16
            if (i % p == 0) break;
17
        }
18
    }
19
}

质因子分解(O(n)筛法,O(logn)质因子分解 )#

质因子分解解释#

✅ 结论公式：

设一个正整数 ( n ) 的 质因子分解 为：

[ n = p_1^{a_1} \cdot p_2^{a_2} \cdot \cdots \cdot p_k^{a_k} ]

那么它的约数个数（包括 1 和 ( n ) 本身）为：

[ \text{约数个数} = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1) ]

1
vector<int> pri;
2
int pmin[N];
3
void my_pmin(int n)
4
{
5
    for (int i = 2; i <= n; i++)
6
    {
7
        if (!pmin[i])
8
        {
9
            pmin[i] = i; // pmin[i]：i 的最小质因子
10
            pri.push_back(i);
11
        }
12
        for (auto p : pri)
13
        {
14
            if (i * p > n) break; // 超范围了
15
            pmin[i * p] = p;
16
            if (i % p == 0) break;
17
        }
18
    }
19
}
20

21
ve<pii> nszka(int n)
22
{
23
    map<int, int> mp;
24
    while (n != 1)
25
    {
26
        int pm = pmin[n];
27
        mp[pm]++;
28
        n /= pm;
29
    }
30
    ve<pii> f;
31
    for (auto [x, y] : mp) f.push_back({x, y});
32
    return f;
33
}
34
// 示例：分解 60 -> [(2,2), (3,1), (5,1)]

矩阵的转置 (横向变纵向，纵向变横向)#

1
ve<ve<int>>a(n+1,ve<int>(n+1));
2
ve<ve<int>>b(n+1,ve<int>(n+1));
3
for(int i=1;i<=n;i++)
4
{
5
    for(int j=1;j<=n;j++)
6
    {
7
        b[i][j]=a[j][n-i+1];
8
        // cout<<"("<<i<<", "<<j<<")  ("<<j<<", "<<n-i+1<<")  \n";
9
    }
10
}
11
a=b;

组合数( 快速幂+组合数+逆元预处理 O(n) )#

✅ 问题形式：(能使用乘法逆元的前提)#

要求的是：

[ \frac{a}{b} \mod m ]

若：

[ \gcd(b, m) = 1 ]

则 ( b ) 在模 ( m ) 意义下有乘法逆元 ( b^{-1} \mod m )，于是可以转化为：

[ \frac{a}{b} \mod m \equiv a \cdot b^{-1} \mod m ]

1
int ksm(int a, int n)
2
{
3
    int ans = 1;
4
    while (n)
5
    {
6
        if (n & 1) ans = ans * a % mod;
7
        a = a * a % mod; n >>= 1;
8
    }
9
    return ans;
10
}
11
struct ZHS
12
{
13
    int fac[N+2], ifac[N+2];
14
    ZHS() { init(); }
15
    void init()
16
    {
17
        fac[0] = ifac[0] = 1;
18
        for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % mod;
19
        ifac[N] = ksm(fac[N], mod - 2);
20
        for (int i = N - 1; i >= 1; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod;
21
    }
22
    int C(int n, int m)
23
    {
24
        if (n >= m && m >= 0 && N > n)
25
            return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
26
        return 0;
27
    }
28
    int A(int n, int m)
29
    {
30
        if (n >= m && m >= 0 && N > n)
31
            return fac[n] * ifac[n - m] % mod;
32
        return 0;
33
    }
34
} zhs;
35

36
int inv(int a,int mod) { return ksm(a,mod-2,mod);}

扩展欧几里得exgcd#

求解形如 ax+by==gcd(a,b) 的不定方程的任意一组解

1
int exgcd(int a,int b,int&x,int& y)
2
{
3
    if(b!=0)
4
    {
5
        x=1;y=0;
6
        return a;
7
    }
8
    int d=exgcd(b,a%b,y,x);
9
    y-=a/b*x;
10
    return d;
11
}

杨辉三角#

杨辉三角模板题#

杨辉三角具有如下的初始条件：

$C_{i,0} = C_{i,i} = 1$

杨辉三角有如下的递推公式：

$C_{i,j} = C_{i-1,j} + C_{i-1,j-1}$

杨辉三角本质是二项式系数，其第 $n$ 行各个数值即为 $(a+b)^n$ 展开后各项的系数。
展开后共有 $n+1$ 项，第 $i$ 项的系数记作 $C_{n,i}$ ，形如：

$C_{n,0}a^n + C_{n,1}a^{n-1}b + C_{n,2}a^{n-2}b^2 + \dots + C_{n,n-1}ab^{n-1} + C_{n,n}b^n$

由于 $a^n$ 只能由 $n$ 个 $(a+b)$ 中 $a$ 相乘得到，因此其系数为 $1$ ， $b^n$ 同理，由此得到了杨辉三角的边界条件式。

对于杨辉三角第 $n$ 行中第 $i$ 项 $C_{n,i}$ ，其为 $a^i b^{n-i}$ 的系数。
考虑第 $n$ 行的 $a^i b^{n-i}$ 可能来源：

$(a+b)^n = (a+b)^{n-1}(a+b)$

即：

$(C_{n-1,0}a^{n-1} + C_{n-1,1}a^{n-2}b + \dots + C_{n-1,n-1}b^{n-1})(a+b)$

于是 $a^i b^{n-i}$ 可以由上一行的 $a^{i-1}b^{n-i}$ 乘以 $a$ ，或者由 $a^i b^{n-i-1}$ 乘以 $b$ 得到。
由此可得：

$C_{n,i} = C_{n-1,i-1} + C_{n-1,i}$

即杨辉三角的递推式。

由于二项式系数的组合性质，杨辉三角的 $C_{i,j}$ 项即为组合数 $C(i,j)$ ，这使得杨辉三角成为时间复杂度允许情况下一种简洁好写的组合数求法。

1
#include <cstdio>
2
int N,C[30][30];
3
int main()
4
{
5
    scanf("%d",&N);
6
    int i,j;
7
    C[0][0]=1;printf("1\n");
8
    for(i=1;i<=N;i++)
9
    {
10
        for(j=1;j<=i;j++)
11
        {
12
            C[i][j]=C[i-1][j]+C[i-1][j-1];
13
            printf(j!=i?"%d ":"%d\n",C[i][j]);
14
        }
15
    }
16
}