「学习笔记」数学大礼包

阅读量：5323 次

发布时间：2019-06-14

本文共 7165 字，大约阅读时间需要 23 分钟。

数论函数

狄利克雷卷积

$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$

积性函数

若满足$(a,b)=1$，$f(a)f(b)=f(ab)$的数论函数$f$叫做积性函数

性质：若$f, g$为积性，$f*g$也为积性

证明：$a,b$为任意互质正整数，$(f*g)(a)(f*g)(b)=\sum_{d|a} f(d)g(\frac{a}{d})\sum_{d'|b} f(d')g(\frac{b}{d'})$

考虑到对于每一对$d,d'$，都满足$(d,d')=1$，且乘积$dd'$取遍$ab$不同的约数，

根据$f(d)g(\frac{a}{d})f(d')g(\frac{b}{d'})=f(d)f(d')g(\frac{b}{d'})g(\frac{a}{d})=f(dd')g(\frac{ab}{dd'})$

得$(f*g)(a)(f*g)(b)=(f*g)(ab)$

线性筛

积性函数两种筛法：

考虑$f(p^c)$到$f(p^{c+1})$

考虑找到$k|i,(k,p)=1$，$f(ip)=f(k)f(\frac{ip}{k})$

莫比乌斯反演

套路：

枚举最大公约数$d$

枚举两个数的乘积$T$

转成下取整乘卷积函数g的结构，回答可以$O(\sqrt n)$，预处理暴力$O(n\log n)$或$O(n)$线筛

杜教筛

求$S(n)=\sum_{i=1}^n f(i)$

若是$f$是积性函数，并且你能找到一个函数$g$,满足$g(1)\not=0$，$g$和$f*g$（记作函数$h$）能快速求和，就能使用杜教筛

\[\sum_{i=1}^n h(i)\]

\[=\sum_{i=1}^n \sum_{d|i}g(d)f(\frac{i}{d})\]

\[=\sum_{d=1}^n g(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}f(i)\]

\[=\sum_{d=1}^n g(d) S(\lfloor \frac{n}{d} \rfloor)\]

把关于$S(n)$的一项拿出来，再通过小学数学变形得：

\[S(n)=\frac{\sum_{i=1}^n h(i)-\sum_{d=2}^ng(d)S(\lfloor \frac{n}{d} \rfloor)}{g(1)}\]

这个直接记忆化求是$O(n^{\frac{3}{4}})$，用定积分可以求得。如果预处理前$n^{\frac{2}{3}}$项，复杂度就是$O(n^{\frac{2}{3}})$

数论

同余

证明：若$ac \equiv bc \pmod p$，则$a \equiv b\pmod {\frac{p}{\gcd(c, p)} }$

$ac-bc\equiv 0 \pmod p$

$c(a - b)\equiv 0 \pmod p$

$p \mid c(a - b)$

$\frac{p}{\gcd(c, p)} \mid \frac{c}{\gcd(c, p)} (a - b)$

因为$\frac{p}{\gcd(c, p)}$ 与 $\frac{c}{\gcd(c, p)}$ 互质（$\gcd$的定义）

所以$\frac{p}{\gcd(c, p)} \mid (a - b)$

$a \equiv b\pmod {\frac{p}{\gcd(c, p)} }$

辗转相除法

证明：$\gcd(a, b) = \gcd(b, a \bmod b)$

等价于证明：$\gcd(a, b) = \gcd(b, a - b)$

利用公因数小于等于其最大公约数的性质

令$d=\gcd(a, b), d'=\gcd(b, a - b)$

$d \mid a, d \mid b$，因此$d \mid a - b$，所以$d\leq d'$

$d' \mid b, d \mid a - b$，因此$d \mid a$，所以$d'\leq d$

因此$d=d'$，得证

扩展欧几里得算法

证明方程$ax+by=\gcd(a, b)$存在一组整数解$x, y$。

若$bx + (a \bmod b)y = \gcd(b, a \bmod b)$有解，进行重组：

$bx + (a - \lfloor \frac{a}{b} \rfloor\times b)y=\gcd(a, b)$

$bx + ay - \lfloor \frac{a}{b} \rfloor\times b \times y=\gcd(a, b)$

$ay + b(x - \lfloor \frac{a}{b} \rfloor \times y) =\gcd(a, b)$

可以构造出$ax+by=\gcd(a, b)$的解

因此可以一直递归，直到某个数为$0$，这时候显然有整数解，所以原方程也是有整数解的

可以得到简单推论：$a$在模$p$意义下存在逆元的条件是$\gcd(a, p)=1$

欧拉函数

证明：$1$到$n$中与$n$互质的数的个数$\varphi(n)=n\prod_{p_i}(1 - \frac{1}{p_i})$

每个素因子的倍数与$n$不互质，应该减去，但是有些数是多个素因子的倍数，因此需要容斥

$\varphi(n)=n - \lfloor \frac{n}{p_1} \rfloor - \lfloor \frac{n}{p_2} \rfloor - ... + \lfloor \frac{n}{p_1p_2} \rfloor + ...$

考虑每个素因子要是选，分母乘以它，这一项变号；不选相当于乘以$1$。于是得到上述式子。

证明：与$n$互质的数之和为$\frac{n\varphi(n)}{2}$

若$\gcd(d, n)=1$，则$\gcd(n, n - d) = 1 $，即互质的数两两出现，且和为 $n$

可以证明$d\not = n - d$，若相等则$2d=n$，不互质

欧拉定理：若$(a, m)=1,a^{\varphi(m)}=1\pmod m$

证明：任取缩系$r_1, r_2, ..., r_{\varphi(m)}$

$(a, m)=1$，则$ar_1, ar_2, ..., ar_{\varphi(m)}$也是一个缩系

$r_1r_2...r_{\varphi(m)}\equiv ar_1ar_2...ar_{\varphi(m)} \pmod m$

每个$r$与$m$互质，存在逆元，两边同时约去，得证

特殊情形：$a^{p-1}=1\pmod p$

扩展欧拉定理：$a^b=a^{\min(b, b\bmod \varphi(m)+\varphi(m))} \pmod m$

中国剩余定理及拓展

求解线性同余方程组

\[ \begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \cdots \\ x \equiv a_n \pmod {m_n} \end{cases} \]

若$m_1, m_2, \cdots, m_n$两两互质

使用中国剩余定理crt构造。

令$M = \prod m_i, k_i=\frac{M}{m_i}$，记$k_i^{-1}$表示$k_i$在$\bmod m_i$意义下的逆元，

方程组的解为：$x=\sum_{i = 1}^n a_i k_i k_i^{-1}$

每个$a_i$的系数，当不是$\bmod m_i$的时候都会是$0$（整除），$\bmod m_i$的时候为$1$（逆元的定义），巧妙构造出解

若$m_1, m_2, \cdots, m_n$不一定两两互质

使用拓展中国剩余定理

考虑如何合并方程$x \equiv a \pmod b,x\equiv c\pmod d$

令$x=bt + a$

$bt + a \equiv c\pmod d $

$bt \equiv c - a \pmod d$

使用exgcd解出$t\equiv t_0\pmod {\frac{d}{\gcd(b,d)}}$

再带回去就能得到$x$

于是我们可以通过$n-1$次合并解出上述同余方程组

若exgcd时出现无解就意味着同余方程组无解

BSGS和exBSGS

离散对数：$a^x\equiv b \pmod p$

考虑$\gcd(a, p) = 1$时：BSGS算法

令$m = \lceil \sqrt p \rceil$

假设$x$是解，则$x$一定可以表示为$x = mq + r,m\in[0, m], r \in[0, m - 1]$

$ax^{mq+r}\equiv b \pmod p$

$ax^{mq}\equiv ba^{-r} \pmod p$

我们枚举$q$把左边存入hash表，再枚举右边的$r$，查询有没有对应的$q$

注意最好手写hash表，或者unordered_map

复杂度为$O(\sqrt p \log p)$

实际中其实可以灵活调整$m$的大小优化复杂度

若$\gcd(a, p)\not = 1$时候，使用exBSGS算法。

令$d = \gcd(p, a)$，等式两边不断同时约去$d$，直到$d=1$

$a^x\equiv b \pmod p$

约一次：$a^{x-1}\frac{a}{d}\equiv \frac{b}{d} \pmod {\frac{p}{d}}$

直到$a,p$互质以后：$a^{x-t}\frac{a^t}{\prod d}\equiv \frac{b}{\prod d} \pmod {\frac{p}{\prod d}}$

把左边$\frac{a^t}{\prod d}$移到右边（此时一定存在逆元）,使用BSGS求解，然后答案加上$t$

注意约的时候要特判，$d$不整除$b$无解，如果出现左边等于右边，答案就是$t$

每次约分$p$至少减小一半（$d\geq 2$），所以这个过程只是带一个$\log$而已

#include 
    
     #include 
     
      #include 
      
       using namespace std;namespace Map {    const int mod = 76543;const int N = 1e5 + 10;int cnt, hd[mod], nxt[N], fir[N], sec[N];void clr() {    fill(hd, hd + mod, -1); cnt = 0;}void ins(int x, int y) {    int k = x % mod;    fir[cnt] = x; sec[cnt] = y; nxt[cnt] = hd[k]; hd[k] = cnt ++; }int find(int x) {    for(int i = hd[x % mod]; ~ i; i = nxt[i])        if(fir[i] == x) return sec[i];    return -1;}}int gcd(int a, int b) {    return b ? gcd(b, a % b) : a;}void exgcd(int a, int b, int &x, int &y, int &g) {    if(!b) x = 1, y = 0, g = a;    else exgcd(b, a % b, y, x, g), y -= a / b * x;}int qpow(int a, int b, int p) {    int ans = 1;    for(; b >= 1; b >>= 1, a = 1ll * a * a % p)        if(b & 1) ans = 1ll * ans * a % p;    return ans;}int inv(int a, int p) {    int x, y, g; exgcd(a, p, x, y, g);    return g == 1 ? (x % p + p) % p : -1;}int logM(int a, int b, int p) { //a^x c = b (mod p), (a, p) = 1    Map :: clr();    int m = (int) ceil(sqrt(p + 0.5));    int aM = qpow(a, m, p), t = 1;    for(int i = 0; i <= m; i ++) {        if(-1 == Map :: find(t)) Map :: ins(t, i);        t = 1ll * t * aM % p;    }    int q = b, inv_a = inv(a, p), ans = -1;    for(int i = 0; i < m; i ++) {        if(~ (t = Map :: find(q))) {            int r = t * m + i;            if(ans == -1 || ans > r) ans = r;        }        q = 1ll * q * inv_a % p;    }    return ans;}int exlogM(int a, int b, int p) { //a^x = b (mod p)    if(b == 1) return 0;    int d = gcd(a, p), t = 0, l = 1;    while(d > 1) {        if(b % d) return -1;        b /= d; p /= d; t ++;        l = 1ll * l * (a / d) % p;        if(l == b) return t;        d = gcd(a, p);    }    b = 1ll * b * inv(l, p) % p;    int q = logM(a, b, p);    return ~ q ? q + t : -1;}int main() {    int x, z, k;    while(~ scanf("%d%d%d", &x, &z, &k) && x && z && k) {        int res = exlogM(x % z, k, z);        if(res == -1) puts("No Solution");        else printf("%d\n", res);    }    return 0;}

阶和原根和指标

若$(a, p) = 1$，满足$1\leq x < n,a^x\equiv 1 \pmod p$的最小正整数$x$称为$a$在模$p$的阶

若$g$在模$p$的阶为$\varphi(p)$，则称$g$为$p$的原根

若$0 \leq x < \varphi(p), g^x\equiv a\pmod p$，称$x$为以$g$为底模$n$的一个指标

组合

组合数

容斥

$|S_1\cup S_2 \cup S_3 ... \cup S_n|=\sum_{i = 1}^n|S_i|-\sum_{1 \leq i < j \leq n} |S_i \cap S_j| + ...$

$|S_1\cap S_2 \cap S_3 ... \cap S_n|=U -|\overline{S_1}\cup\overline{S_2} \cup \overline{S_3} ... \cup\overline{S_n}|$

矩阵

单位矩阵$I$

\[ \begin{bmatrix} 1 & 0 & 0 & \cdots & 0\\ 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots & 1\\ \end{bmatrix} \]