Update on 2023.08.19：修改了一处笔误
Update on 2023.11.03：增添内容
Update on 2023.12.15：因数部分

注：远古作品，写的很垃圾

数论

线性筛

bitset<100000> vis;
vector<int> p;

void init() {
    p.push_back(-1);
    for (int i = 2; i <= 100000; i++) {
        if (!vis[i]) p.push_back(i);
        for (int j = 1; j <= p.size() && i * p[j] <= 100000; j++) {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}

通过给上面的代码添加一点小小的修改，我们就可以得到了一个既能筛质数，也能分解质因子的函数

int n, T, p[maxn / 10], Min[maxn];      //Min中存的元素便是一个数最小的质因子
void GetPrime() {
    for (int i = 2; i <= maxn; i++) {
        if (!vis[i]) {
            p[++p[0]] = i;
            Min[i] = i;
        }
        for (int j = 1; j <= p[0] && 1ll * i * p[j] < maxn; j++) {
            vis[i * p[j]] = 1;
            Min[i * p[j]] = p[j];
            if (i % p[j] == 0)
                break;
        }
    }
}

给定一个数然后求出它所有的质因子。

cin >> x;
while(x > 1)  x /= Min[x];

这么做一定是可行的，利用了算术基本定理。

他的更多扩展用法：

$pri_i$：编号为 $i$ 的质数。

$mi_i$ ：$i$ 的最小质因子。

$phi_i$： $\varphi(i)$ 的值（欧拉函数）。

$mu_i$：$\mu(i)$ 的值（莫比乌斯函数）。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20000000 + 5;

int pri[maxn], phi[maxn], mi[maxn], mu[maxn];
bitset<maxn> vis;

void init(){
    mu[1] = 1;
    for(int i = 2; i <= maxn - 5; i++) {
        if(!vis[i]) pri[++pri[0]] = i, mi[i] = i, phi[i] = i - 1, mu[i] = -1;
        for(int j = 1; j <= pri[0] && i * pri[j] <= maxn - 5; j++) {
            int tt = i * pri[j];
            vis[tt] = 1;
            mi[tt] = pri[j];
            if(i % pri[j] == 0) {
                phi[tt]  = phi[i] * pri[j];
                break;
            }
            else phi[tt] = phi[i] * phi[pri[j]];
            mu[tt] = -mu[i];
        }
    }
}

int main() {
    freopen("a.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    printf("%d\n", mu[6]);
    
    return 0;   
}

当然，筛法还能有更多的应用，他还能在因子上下功夫。

唯一分解定理

$$n = \prod_{i=1}^{m} p_{i}^{k_i}$$

唯一分解定理与 LCM、GCD 之间的关系

设有两个数：$a = \prod_{i=1}^{m_a} pa_{i}^{ka_i}$ 、$b = \prod_{i=1}^{m_b} pb_{i}^{kb_i}$，则有：

它们的 $\gcd$ 为二者 $k$ 取 $\min$ ，而 $lcm$ 为二者的 $k$ 取 $\max$

因子

因子和

由算数基本定理可得，一个数 $n$ 一定可以被以下的式子表示出来：

$$n = \prod_{i=1}^{m} p_{i}^{k_i}$$

后文中默认 $p$ 从小到大排序并编号
其中 $p$ 是质数，$k$ 是一个非负整数，$m$ 表示该数最少可以被几个素数表示，试求：

$$\sum_{d|n}^{}d $$

通过一系列的推到可以得出

$$\sum_{d|n}^{}d = \prod_{i=1}^{m} \sum_{j=0}^{k_i} p_i^j$$

推到过程如下：

对于每一个质数 $p_i$ 他的不同次方可以构成一个集合，笔者拿 $360$ 来举例：

已知 :

$$360 = 2^3\cdot3^2 \cdot5^1$$

$360$ 被分解成了三个质数，那么其所有的因数都能通过这三个质数不同次幂的乘积表示。例如 $2^1\cdot3^0 \cdot5^0$，$2^1\cdot3^0 \cdot5^1$，$2^2\cdot3^1 \cdot5^0$ ，等等。像这样的数，都是 $360$ 的因数。

其因数和等于：

$$2^0 \cdot 3^0 \cdot 5^0 + 2^0 \cdot 3^0 \cdot 5^1 + 2^0 \cdot 3^1 \cdot 5^0 + 2^0 \cdot 3^1 \cdot 5^1 + 2^0 \cdot 3^2 \cdot 5^0+ \cdots + 2^3 \cdot 3^2 \cdot 5^1$$

化简可得：

$$(1 + 2^1 + 2^2 + 2^3)\cdot(1+3^1+3^2) \cdot (1+5^1) = \prod_{i=1}^{3} \sum_{j=0}^{k_i} {p_i}^j $$

推导完毕。

代码实现

问题描述

给定一个数 $n$ 求 $[1,n]$ 中所有数的因子和。

分析与解答

为了在 $O(n)$ 的时间复杂度内解决问题，上述题目可以通过线性筛来解决；

我们定义 $f_i$，代表 $i$ 的因子和。

定义 $g_i$ 代表：

$$\sum_{j=0}^{k_1} {p_1}^j$$

我们该如何处理这两个数组？

对于每次循环得到的 $i$，若 $i$ 是质数（情况一），$f_i = i + 1$ ，$g_i = i + 1$。不做过多赘述。

否则，我们已经知道了 $i$ 的唯一分解式，有两种情况需要我们考虑：

定义 $t = i\times prime_j$

若 $i$ 的唯一分解式中不含 $prime_j$ 时，也就是 $i$ 模 $prime_j$ 不为 $0$ 时（情况二）。

则 $g_t = prime_j+1$， $f_t = f_i \times g_t$。

举一个例子：

若此时 $i$ 的唯一分解式为 $3^2\cdot5^1$，$prime_j=2$，满足情况二。此时 $t$ 的唯一分解式为 $3^3\cdot4^1$， $g_i = 1+3^1+3^2$，$f_i = (1+3^1+3^2)\times(1+5^1)$。

经过推导可知：

$$g_t = 1 + 2 = 1 + prime_j$$

$$ f_t = (1+2^1)\times(1+3^1+3^2)\times(1+5^1) = g_t\times f_i$$

若 $i$ 的唯一分解式中包含 $prime_j$ 时，也就是 $i$ 模 $prime_j$ 为 $0$ 时（情况三）。

则 $g_t = g_i \times prime_j + 1$， $f_t = \frac{f_i \times g_t}{g_i}$

举一个例子：

若此时 $i$ 的唯一分解式为 $2^2\cdot3^1$，$prime_j=2$，满足情况三。此时 $t$ 的唯一分解式为 $2^3\cdot3^1$， $g_i = 1+2^1+2^2$，$f_i = (1+2^1+2^2)\times(1+3^1)$。

经过推导可知：

$$g_t = 1+2^1+2^2+2^3=(1+2^1+2^2)\times2+1=g_i\cdot prime_j+1$$

$$f_t= (1+2^1+2^2+2^3)\times(1+3^1) = \frac{(1+2^1+2^2)\times(1+3^1)}{(1+2^1+2^2)}\times (1+2^1+2^2+2^3) =\frac{f_i }{g_i}\times g_t$$

参考代码

void sol() {
    for(int i = 2; i <= n; i++) {
        if(!vis[i]) p[++p[0]] = i, f[i] = g[i] = 1 + i;//情况一
        for(int j = 1, t; (t = i * p[j]) <= n && j <= p[0]; j++) {
            vis[t] = 1;
            if(i % p[j]) g[t]  = p[j] + 1, f[t] = f[i] * g[t]; //情况二
            else {  //情况三
                g[t] = g[i] * p[j] + 1;
                f[t] = f[i] / g[i]  * g[t];
                break;
            }
        }
    }
}

不定方程

定义

形如 $ax + by = c$，其中 $a, b, c$ 是已知数的方程被称为二元一次不定方程。

求解

定理：方程 $ax + by = c$ 有解当且仅当 $gcd(a, b) | c$
先考虑如何求 $ax + by = gcd(a, b)$

$$ax + by = gcd(a, b)$$

$$= gcd(b, a \bmod {b}) $$

$$=bx′ + (a \bmod {b})y′$$

$$=bx′ + (a − ⌊ \frac{a}{b}⌋ × b)y′$$

$$=y′ + b(x′ − ⌊\frac{a}{b}⌋y′)$$

其中 $x′$ 和 $y′$ 是不定方程 $bx + (a \bmod {b})y = gcd(b, a \bmod {b})$的解。

如果求出了 $x′$ 和 $y′$，就可以根据对应系数相等算出 $x = y′$，$y = x′ − ⌊ \frac{a}{b}⌋y′$。

同余

对两个整数 $a, b$，如果它们除以 $d$ 的余数相同，则称它们模 $d$ 同余，记作:

$$a \equiv b \enspace(\bmod{d})$$

威尔逊定理

正整数 $p$ 是质数的充要条件为 $(p − 1)! ≡ −1 (\bmod p)$。

欧拉函数

定义

定义欧拉函数 $\varphi(n)$ 表示小于 $n$ 的数中与 $n$ 互质的数的个数；特别的，$\varphi(1) = 1$。

性质

积性：如果 $gcd(a, b) = 1$，则 $\varphi(a × b) = \varphi(a) × \varphi(b)$。

欧拉反演：$\sum_{d|n} \varphi(d) = n。$

性质3：对任意实数$p，\varphi(p^k) = p^k − p^{k−1}$。

计算

单个欧拉函数：设 $n$ 的唯一分解式是：

$$n = p_1^{k_1} p_2^{k_2} \cdots p_s^{k^s}$$

由性质3可得

$$\varphi (n) = {\textstyle \prod_{i=1}^{s}\varphi(p_i^{k_i})} $$

线性欧拉函数：在线性筛的同时可以筛出欧拉函数，设 $p$ 是 $i$ 的最小质因子，分三种情况讨论：

$i$ 为质数：$\varphi (i) = i − 1$
$p$ 是 $\frac{i}{p}$ 的质因子：$\varphi (i) = \varphi(\frac{i}{p}) × p$。
$p$ 和 $\frac{i}{p}$ 互质：$\varphi(i) = \varphi(\frac{i}{p})\varphi(p)$。

我真的受不了了！！！一个晚上就只写了这么点。数论真™毒瘤QAQ$\enspace\enspace\enspace\enspace$–20230815

逆元

定义

在模 $p$ 同余下，对每个 $x$，能找到一个整数 $x^{−1} ∈ [1, p)$，使任何数除以 $x$ 等价于乘 $x^{−1}$。这样的 $x^{−1}$ 称为 $x$ 在模 $p$ 同余下的逆元。

显然，逆元 $x$ 应满足 $xx^{−1} ≡ 1 (\bmod p)$。

以容易理解的角度来讲：对于任意整数 $x(\bmod{p})$ 的逆元表示为：

$$x^{-1}(\bmod n)$$

逆元存在性定理：$x$ 在模 $p$ 同余下存在逆元当且仅当 $gcd(x, p) = 1$

可通过反证法进行证明，若需详细步骤请自行查阅资料。

性质

定理：模 $p$ 同余下，一个整数 $x$ 的逆元若存在，则唯一。
证明：考虑反证法；假设 $x$ 有两个不同的逆元 $i_1，i_2$，满足 $xi_1 \equiv 1 \pmod{p} $，$xi_2 \equiv 1 \pmod{p} $。根据同
余的传递性，$xi_1 \equiv xi_2 \pmod{p} $在同余号两侧左乘 $i_1$，得到：$(i_1x)i_1 ≡ (i_1x)i_2\pmod p ⇐⇒ 1i_1 ≡ 1i_2 \pmod p$

定理：在模质数 $p$ 同余下，$[1, p − 1]$ 内所有整数的逆元互不相同。
证明：反证，假设 $x$, $y$ 的逆元均为 $i$，则 $x_i ≡ y_i \pmod p$。两侧同乘 $i^{−1}$ 立得 $x ≡ y \pmod p$，矛盾。

定理：一个数的逆元的逆元等于它自身。
证明：由模意义下乘法交换律和结合律立得。

通过扩展欧几里得(exgcd) 计算逆元

对任意给定的 $x$ 和 $p$，显然 $x × x^{−1} ≡ 1 \pmod p$ 可以利用这个式子计算 x^{−1}。

上式等价于 $xx^{−1} = kp + 1 ⇐⇒ xx^{−1} + pk = 1$。

其中 $x$ 和 $p$ 是已知量，所以上式是一个不定方程，$x^{−1}$ 和 $k$是变量。用 $exgcd$ 求解可以得到 $x^{−1}$。

根据不定方程有解的条件，$gcd(x, p) | 1 ⇐⇒ gcd(x, p) = 1$。这和逆元存在性定理也是相适应的。

欧拉定理

欧拉定理 (Euler Theorem)：对任意正整数 $a$, $m$ 且 $gcd(a, m) = 1$，一定有：$a^{\varphi (m)} ≡ 1 \pmod m$

证明自行查阅资料

费马小定理

费马小定理（Fermat’s Little Theorem）：对任意整数 $a$ 和质数 $p$，$a^{p−1} ≡ 1 \pmod p$。

证明请自行查阅资料

通过费马小定理求逆元

根据费马小定理，$a^{p−1} ≡ 1\pmod p$。

两侧同乘 $a^{−1}$，得到 $a^{−1} ≡ a^{p−2} \pmod p$。

这就得到了逆元的第二种求法：快速幂求出 $a^{p−2}\pmod p$即可。

设 $inv_i$ 表示 $i$ 的逆元，有递推式：

$ inv_{i} ≡ − ⌊\frac{p}{i} ⌋ × inv _{p \mod i} \pmod p $

边界为 $inv_1 = 1$。

中国剩余定理

中国剩余定理问题

我们给定 $N$ 个线性同余方程组：

${\begin{matrix} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ \dots \\ x \equiv a_{n} (\mod m_{n}) \end{matrix}$

其中保证 $m_1, m_2, \dots ,m_n$ 两两互质。求 $x$ 的通解

定理

中国剩余定理 (Chinese Remainder Theoremm, CRT)：上页方程组有解，且按如下方式构造：

记 $M = \prod m_i，M_i = m{\div m_i} $，$t_i$ 是 $M_i$ 在模 $m_i$ 群下的逆元。

则该方程的唯一通解是：

$$x \equiv \sum_{i=1}^{n} a_it_iM_i \pmod{M} $$

举例来说：对于以下线性同余方程组：

${\begin{matrix} x \equiv 1 (\mod 5) \\ x \equiv 2 (\mod 5) \\ x \equiv 3 (\mod 7) \end{matrix}$

$$M = 3\cdot 5\cdot 7=105$$

$$M_1=M/3=105/3=35$$

$$M_2=105/5=21$$

$$M_3=105/7=15$$

接下来为了确定 $t_i$ 我们需要解以下同余方程：

$$M_it_i \equiv 1 \pmod{m_i}$$

所以说我们可以得到：

${\begin{matrix} 35 t_{1} \equiv 1 (\mod 3) \\ 21 t_{2} \equiv 1 (\mod 5) \\ 15 t_{3} \equiv 1 (\mod 7) \end{matrix}$

我们可以解得：

${\begin{matrix} t_{1} = 2 \\ t_{2} = 1 \\ t_{3} = 1 \end{matrix}$

最后我们通过上面的那个式子可以算出：

$$x \equiv 1\cdot 2\cdot 35+2\cdot 1\cdot 21+3\cdot 1\cdot 15 \equiv157\equiv52 \pmod{105}$$

故 $x = 52$

组合数学

排列组合常用公式

从m个东西中

排列数(在乎顺序)：$A^m_n=\frac{n!}{(n-m)!} $

组合数（不在乎顺序）：$C^m_n = \frac{ {\textstyle \prod_{n-m+1}^{n}}}{m!}$

简化公式的推理如下:

$$C^m_n=\frac{n!}{m!(n-m)!} $$

$$= \frac{ {\textstyle \prod_{1}^{n}} }{{\textstyle \prod_{1}^{m} } {\textstyle \prod_{1}^{n-m} }}$$

$$= \frac{ {\textstyle \prod_{1}^{n-m}}{\textstyle \prod_{n-m+1}^{n}} }{{\textstyle \prod_{1}^{m} } {\textstyle \prod_{1}^{n-m} }}$$

$$= \frac{ {\textstyle \prod_{n-m+1}^{n}} }{{\textstyle \prod_{1}^{m} }}$$

$$= \frac{ {\textstyle \prod_{n-m+1}^{n}}}{m!}$$

隔板法：$C^{m-1}_{n+m-1}$

错位排列公式：$D_n=(n-1)*(D_{n-1}+D_{n-2})$

一个数列的全排列的个数是数列的数的个数的阶乘除以每个数出现的次数的阶乘

**以上公式的详细证明请自行搜索（或者有空了我在写）*

运用费马小定理求解组合数

求解 $C^m_n \mod p $ ($p$ 为质数) 的值

已知：

$$C^m_n=\frac{n!}{m!(n-m)!} $$

可以转化为 $n!$ 乘上 $m!(n-m)!$ 的逆元

由前文费马小定理可知一个数 $a \mod p$ 的逆元就是 ${a!}^{p-2}$

用代码实现非常的轻松：

typedef long long ll;
const int mod = p; //p是质数

int fac[maxn], inv[maxn]; // fac[i]，inv[i] 分别代表 i! 和 i 的逆元

ll QuiclPow(ll x, ll y) { //快速幂
    ll ans = 1;
    while(y != 0) {
        if(y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}

void init() {
    fac[0] = 1;
    //inv[0] = 1;
    for(int i = 1; i <= maxn - 5; i++) {
        fac[i] = fac[i - 1] * i % mod; //计算阶乘
        inv[i] = QuiclPow(fac[i], mod - 2); //费马小定理求解逆元
    }
}

知道了逆元之后我们也知道了阶乘，就可以愉快的求出组合数了awa

C = fac[n] * inv[m] % mod * inv[n - m] % mod;

线性代数

矩阵

通俗易懂的说，矩阵在 OI 中就是一个二维数组。

矩阵乘法

对于一个矩阵 $A$：

$$\begin{bmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\end{bmatrix}$$

一个矩阵 $B$：

$$\begin{bmatrix} b_{11} & b_{12}\\ b_{21} & b_{22}\\ b_{31} & b_{32}\end{bmatrix}$$

矩阵 $C$ 为 $A、B$ 的乘积，记为 $C = A \times B$ 。

$A$ 的行数列数分别为 $n、m$ ，$B$ 的行数列数分别为 $x、y$。

当且仅当 $m=x$ 的时候两个矩阵才能相乘，矩阵乘法不满足乘法交换律，但满足乘法结合律。因为若交换两个矩阵，原先的限制条件变为 $n=y$ 不一定成立。

新矩阵的表示方法如下：

$$\sum_{i=1}^{n} \sum_{j=1}^{y}c_{ij}=\sum_{k_1}^{m或x} a_{ik} \times a_{k_j}$$

通俗易懂的来说：

$$\begin{bmatrix} a_{11}\times b_{11} + a_{12}\times b_{21} + a_{13}\times b_{31}& \cdots \\ \cdots & a_{21}\times b_{12} + a_{22}\times b_{22} + a_{23}\times b_{32}\end{bmatrix}$$

矩阵加速递推

众所周知，斐波那契数列的递推式如下：

$$F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.$$

当 $n \le 1 \times 10^9$ 时，通过 $O(n)$ 的方法还是可以勉强计算出 $F_n$ 的值的，但当 $n \le 1 \times 10^{18}$ 时呢？很显然这辈子我们都见不到这个问题的答案了。

为了优化这个递推式，我们就可以用到矩阵快速幂，也就是矩阵加速递推的方式来解答。

矩阵乘计算线性递推式时，需要一个数列矩阵和一个参数矩阵。数列矩阵中的一个值就代表着一个项，参数矩阵就是用来转移数列矩阵的矩阵，这样当我们在计算下一个函数值的时候只需要将数列矩阵乘上参数矩阵，通过斐波那契的例子来帮助我们理解这个问题。

数列矩阵如下：

$$\begin{bmatrix}F_n &F_{n-1}\end{bmatrix}$$

已知 $F_{n+1} = F_{n} + F_{n-1}$。
所以参数矩阵为

$$\begin{bmatrix} 1 & 1\\ 1 & 0\end{bmatrix}$$

意味着新的数列矩阵为：

$$\begin{bmatrix} F_n+F_{n-1}& F_n\\\end{bmatrix}$$

就是：

$$\begin{bmatrix} F_{n+1}& F_n\\\end{bmatrix}$$

循环往复，直到得出结果为止，可通过快速幂实现。

你猜猜我是谁

Windows Edge 115.0.1901.203

1 年前
2023-8-17 16:44:39

点赞
你猜猜我是谁

Windows Edge 115.0.1901.203

1 年前
2023-8-17 16:45:08

怎么IP都上去了，气气气
- GGapa
  博主
  你猜猜我是谁
  
  Windows Chrome 116.0.0.0
  
  1 年前
  2023-8-19 21:58:45
  
  你是 $WXC$ 吗？
GGapa
博主
Windows Chrome 116.0.0.0

1 年前
2023-8-19 21:59:42

本文章尚未完成！数论太难了，我搞懂一部分再写一部分QAQ⌇●﹏●⌇
- 你猜猜我是谁
  
  GGapa
  
  Windows Edge 116.0.1938.54
  
  1 年前
  2023-8-23 13:10:45
  
  加油

Year Progress

数论

线性筛

唯一分解定理

唯一分解定理与 LCM、GCD 之间的关系

因子

因子和

代码实现

参考代码

不定方程

定义

求解

同余

威尔逊定理

欧拉函数

定义

性质

计算

逆元

定义

性质

通过扩展欧几里得(exgcd) 计算逆元

欧拉定理

费马小定理

通过费马小定理求逆元

中国剩余定理

中国剩余定理问题

定理

组合数学

排列组合常用公式

运用费马小定理求解组合数

线性代数

矩阵

矩阵乘法

矩阵加速递推

评论

发送评论编辑评论

数论

线性筛

唯一分解定理

唯一分解定理与 LCM、GCD 之间的关系

因子

因子和

代码实现

参考代码

不定方程

定义

求解

同余

威尔逊定理

欧拉函数

定义

性质

计算

逆元

定义

性质

通过扩展欧几里得(exgcd) 计算逆元

欧拉定理

费马小定理

通过费马小定理求逆元

中国剩余定理

中国剩余定理问题

定理

组合数学

排列组合常用公式

运用费马小定理求解组合数

线性代数

矩阵

矩阵乘法

矩阵加速递推

评论

发送评论 编辑评论

推荐文章

发送评论编辑评论