Contents

1 数论

数论

1. 素数

1个大于1的正整数，除了1和它自身外，不能被其他正整数整除的数叫做素数

素数有无限多个

1.1 素数定理

小于x的素数个数近似于$\frac{x}{ln(x)}$

1.2 算数基本定理

$ n = p_1^{a_1} \times p_2^{a_2} \times… \times p_n^{a_n}$ ($p_1,p_2,…,p_n$为素数)

1.3 因数

如果$m$是$n$的因子，那么$\frac{n}{m}$也为$n$的因子，时间复杂度$O(\sqrt{n})$

1.4 筛法筛素数

1.4.1 埃式筛法

notp[1] = 1;
for (int i = 2; i <= n; i++){
    for (int j = i*2; j <= n; j += i)
        notp[j] = 1;
}

1.4.2 线性筛法

notp[1] = 1;
for(int i = 2; i <= n; i ++){
    if(!notp[i])
        pri[++psz] = i;
    for(int j = 1; j <= psz; j++){
        if(i * pri[j] > n)
            break;
        notp[i * pri[j] = 1;
        if(i % pri[j] == 0)
            break;
    }
}

注意：

if(i % pri[j] == 0) break;

保证了每个数只会被最小素因子筛去，去除后会导致复杂度退化为 $n log$ 级

n = 30

15*2  //筛去
10*3  //i=10 j=2(2)时 10%2==0 退出
6*5   //i=6 j=2(2)时 6%2==0 退出

1.4.3 区间筛

枚举[ $1, \sqrt{r}$ ]内的质数
枚举每个质数在区间内的倍数，筛去

for (int i = 1; i <= psz; i ++){
    int p = pri[i];
    for(int j = (l-1) / p + 1; j <= r / p; j ++)
        notp[j * p - l] = 1;  //左移，避免空间浪费
}

2. 模运算

2.1 除法定理

如果$n$, $m$是两个整数， $m \neq 0 $, 存在唯一一对整数$q$和$r$，满足$n = qm+r$ 且 $0 \leq r \leq |m| $

2.2 最大公约数(GCD递归定理)

对于任何非负整数 $a$ 和 $b$ ，$gcd(a,b) = gcd(b, a$ $mod$ $b)$

int gcd(int x, int y){
    return y ? gcd(y, x%y) : x;
}

2.3 裴蜀定理

对任何 $a, b \in Z$ 和它们的最大公约数 $d$ , 关于未知数 $x$ 和 $y$ 的线性不定方程（称为裴蜀等式）: $ax+by=c$ 有整数解($x,y$ ) 当且仅当 $d|c$ ,可知有无穷多解。特别的，一定存在整数 $x$ , $y$ 使 $ax+by=d$ 成立

2.4 算数基本定理推论

两个数相乘等价于指数表示相加

$k = mn \Leftrightarrow k_p = m_p + n_p$

这就蕴含
$ m | n \Leftrightarrow m_p \leq n_p $

这可以推出，对所有的$p$

$ k = gcd(m, n) \Leftrightarrow k_p = min(m_p, n_p)$
$ k = lcm(m, n) \Leftrightarrow k_p = max(m_p, n_p)$

例题1：HDU4497 GCD and LCM

2.5 扩展欧几里得

求解不定方程 $ax+by = gcd(a,b)$，假设( $a \geq b $ )

int exgcd(int a, int b, int &, int &y){
    int d;
    return !b ? (x = 1, y = 0, a) : (d = exgcd(b, a%b, y, x), y -= (a/b) * x, d);
}

设( $x_0,y_0$ )是不定方程 $ax+by=m$ 的一组解，$(a,b)=g$ , 那么全部解为 $(x_0 + \frac{b}{g}t$ , $y_0 – \frac{a}{g}t)$ , 其中 $t$ 为全部整数。

例题2：Luogu1082 同余方程

例题3：Luogu1516 青蛙的约会

例题4：Luogu2421 荒岛野人

2.6 同余关系

若两个整数 $a$ , $b$ 除以 $m$ 有相同的余数，那么称 $a$ , $b$ 对于 $m$同余，记作 $a \equiv b $ $(mod$ $m)$

2.7 逆元

设正整数模 $m$ ,对于任意正整数$a$ 满足 $(a,m)=1$ ，存在 $ab \equiv 1$ ($mod$ $m$ ),称 $b$ 为模 $m$ 意义下的逆元

$O(n)$ 预处理 $1 – n$ 的逆元：

q[1] = 1;
for(int i = 2; i <= n; i ++)
    q[i] = q[i-1] * i % mod;

p[n] = power(q[n], mod - 2);

for(int i = n; i > 1; i --)
    p[i-1] = p[i] * i % mod;

2.8 Miller_Rabin素性测试

2.8.1 费马小定理

设 $p$ 是一个素数， $a$ 是一个整数且不是 $p$ 的倍数，那么 $a^{p-1} \equiv 1 $ ( $mod$ $p$ )

费马小定理的逆命题不成立，但逆否命题成立

2.8.2 二次探测定理

设 $p$ 是素数， $x$ 是一个正整数，且 $ x^2$ $mod$ $p = 1$ ，那么 $ x \equiv \pm 1$ ( $mod$ $p$ )

设待测数为 $n$ ，取一个比 $n$ 小的正整数 $a$，设 $n – 1 = d \times 2^r$ ，若 $n$ 是素数，则要么 $a^d \ mod \ n = 1 $，要么存在一个 $i$ ，满足 $ 0 \leq i < n$ 且 $a^{d\times2^i} \ mod \ n = -1$

随机出若干个 $a$，若全部通过二次探测定理，我们称这个数 $n$ 通过了 Miller_Rabin 测试，是一个质数。

2.9 中国剩余定理

求解一个线性同余方程组 ( $m_1 m_2 … m_n$ 两两互素)

$ x \equiv a_1\ (mod \ m_1) $
$ x \equiv a_2\ (mod \ m_2) $
$ … $
$x \equiv a_n\ (mod \ m_n) $

这个线性同余方程组的解为$ x = \sum_{i=1}^n a_iM_it_i \ ( mod \ M)$ ，$M_i = \frac {M}{m_i}$，$t_i M_i \equiv 1 \ (mod \ m_i )$（ $t_i$ 是 $M_i$ 在模 $m_i$ 下的逆元），$ M = \prod_{i=1}^n m_i $

2.10 中国剩余定理扩展

2.11 整除分块

求 $\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$

通过理论推导（或打表）可以发现 $\lfloor\frac{n}{i}\rfloor$ 出现是呈块状的，并且右端点为 $ n / (n / l) $

for(int l=1,r;l<=n;l=r+1){
    r=n/(n/l);
    ans+=(r-l+1)*(n/l);
}

3. 数论函数

3.1 常见数论函数

$\sigma(n) = \sum_{d | n} d $，表示正整数 $n$ 的正因子之和
$d(n) = \sum_{d | n} 1 $，表示正整数 $n$ 的正因子个数
$\varphi(n)$，表示 $1 – n$ 中与 $n$ 互质的数的个数，称为欧拉函数

3.2 积性函数

如果对任意两个互素的正整数 $n$ 和 $m$，均有 $ f(mn) = f(n)f(m) $，那么数论函数 $f$ 叫作是积性函数

3.3 欧拉函数

性质一：$ \varphi(p^k) = p^k – p^{k-1} = (p-1)p^{k-1} $ （其中 $p$ 是素数）

性质二：$ \varphi(n) $ 是积性函数，但不是完全积性函数

结论一：$ \sum_{d|n} \varphi(d) = n $

3.4 欧拉定理

3.4.1 欧拉定理

设 $n$ 为正整数，$a$ 是与 $n$ 互素的整数，则 $a^{\varphi(n)} \equiv 1 $ ( $mod$ $n$ )

3.4.2. 欧拉定理推论

若正整数 $a$，$n$ 互质，则对于任意正整数 $b$，有 $a^b \equiv a^{b \ mod \ \varphi(n)} $

3.5 莫比乌斯函数

$$ \mu(n)=\begin{cases}
1 & n=1 \\
(-1)^k & n=p_1 p_2 … p_k，p_i为互异素数 \\
0 & otherwise
\end{cases}$$

可知当 $n$ 有平方因子时 $\mu(n) = 0$
莫比乌斯函数是积性函数，因此可以通过线性筛来计算

$\sum_{d|n} \mu(d) = [n = 1]$，其中$[cond]$ 表示 $cond$ 这个条件是否成立

3.6 莫比乌斯反演

$$ F(n) = \sum_{d | n} f (d) \Leftrightarrow f(n) – \sum_{d|n} \mu(d)F(\frac{n}{d})$$
$$ F(n) = \sum_{n | d} f (d) \Leftrightarrow f(n) – \sum_{n|d} \mu(\frac{d}{n})F(d)$$

4. BSGS

5. 原根和指数

(定义 5.1) 设 $(a,m) = 1$，满足 $a^r \equiv 1 \ (mod \ m)$ 的最小正整数 $r$ 叫作整数 $a$ 模 $m$ 的阶

(定理 5.2) 设 $(a,m) = 1$，$r$ 为 $a$ 模 $m$ 的阶，则对于每个正整数 $k$， $a^k \equiv 1 \ (mod \ m)$ 当且仅当 $r\ |\ k$。特别的，$ r\ | \ \varphi(m)$

(推论 5.3) 设 $(a,m) = 1$， $a$ 模 $m$ 的阶是 $r$，当且仅当下列二条件成立：

$a^r \equiv 1 \ (mod \ m)$
对于 $r$ 的每个素因子 $p$ 有 $ a^{\frac{r}{p}} \not \equiv 1 \ (mod \ m)$

(定义 5.4) 若整数 $a$ 模 $m$ 的阶为 $ \varphi(m) $，则 $a$ 叫作是模 $m$ 的原根。

(定理 5.5) 对于正整数 $m$，模 $m$ 具有原根当且仅当 $ m = 2，4，p^a，2p^a$，其中 $p$ 是奇素数且 $ a \geq 1 $

(定义 5.6) 设模 $m$ 有原根 $g$，则 $1，g，g^2，…，g^{\varphi(m)-1}$ 为模 $m$ 的缩系。所以对每个与 $m$ 互素的整数 $a$ ，必存在唯一的整数 $k$ ，时的 $a \equiv g^k \ (mod \ m) $ ，$ 0 \leq k \leq \varphi(m) – 1 $，$k$ 叫作 $a$（对于原根 $g$）模 $m$ 的指数，表示成 $ k = ind_g a$。质数也叫做离散对数

数论

BLOG

数论

数论