数学芝士

longdie · 2020-12-31 14:43:06 · 个人记录

最近开始补数学的锅了。
这次确实写完了。
大概提高组已经勾勒，NOIP前数论部分应该不会再多学了。

update on 11.1:

CSP前，想复习一下基础数论知识，发现自己原来写的出了一堆错，所有的筛法都是从2开始筛, 大家自己注意一下。

update on 9.29:突然知道12月才NOIP，不得不学一些省选知识了。

右键数学公式→Math Settings→Math Renderer→CommonHTML以获得更佳体验。
Markdown数学公式
Markdown

数论部分

质数及相关内容

简介

质数就是只能被1和它本身整除的数，它的个数大概为n\div \ln n个。一些基本性质比如任何数都与1互质，除了2其他的偶数都不是质数等等，比较简单

Eratosthenes筛素数

利用了一个质数的倍数一定不是质数的原理。
复杂度O(nlognlogn)。

int prime[N], tot, vis[N]; //vis[i]表示i不是质数
void shai() {
    for(register int i = 2; i <= n; ++i) {
        if(vis[i]) continue;
        prime[++tot] = i;
        for(register int j = 2; j * i <= n; ++j) {
            vis[i*j] = 1;
        }
    }
}

事实上对于每个质数，我们只需要从x^2开始就可以。

int prime[N], tot, vis[N]; //vis[i]表示i不是质数
void shai() {
    for(register int i = 2; i <= n; ++i) {
        if(vis[i]) continue;
        prime[++tot] = i;
        for(register int j = i; j * i <= n; ++j) {//从i×i开始
            vis[i*j] = 1;
        }
    }
}

线性筛素数

进一步优化Eratosthenes筛素数，使复杂度降为O(n)。
大概原理就是用每个合数的最小质因子筛掉它。

int prime[N], tot, vis[N]; //vis[i]中存i的最小质因子
void shai() {
    for(register int i = 2; i <= n; ++i) {
        if(vis[i] == 0) { vis[i] = i, prime[++tot] = i; }
        for(register int j = 1; j <= tot; ++j) {
            if(prime[j] > vis[i] || prime[j]*i > n) break;//注意是prime[j] > vis[i]
            vis[prime[j] * i] = prime[j];
        }
    }
}

线性筛应该是比赛中用的最多的。

算术基本定理

任何一个大于1的整数都能唯一分解成有限个质数的乘积。

N = p_1^{c^1}P_2^{c^2} ... p_n^{c^n}

质因数分解

一般采用试除法。
就是对1 - \sqrt n 中的每个能整除N的数，把它全部除尽。

int p[N], c[N], tot; //p[i]中存质因子,c[i]存个数。
void divide() {
    for(register int i = 2; i <= sqrt(n + 0.5); ++i) {
        if(n % i == 0) {
            p[++tot] = i;
            while(n % i == 0) {
                n /= i, c[tot]++;
            }
        }
    }
    if(n > 1) p[++tot] = n, c[tot] = 1;//注意别忘了。
}

约数及相关内容

基本内容

若整数n除以整数d的余数为0，那么就说d能整除n，即d|n。

算术基本定理的推论

正整数N被唯一分解为下面的式子：

N = p_1^{c^1}P_2^{c^2} ... p_n^{c^n}

那么N的正约数集合可以表示为：

\{ p_1^{b_1}p_2^{b_2} ... p_n^{b_n} \}，其中0 <= b_i <= c_i

N的正约数个数为：

(c_1 + 1) * (c_2 + 1) * ... * (c_n + 1)

N的所有的正约数的和为：

(1 + p_1 + p_1^2 + ... + p_1^{c_1})*...*(1 + p_n + p_n^2 + p_n^{c_n})

证明应该比较简单。

GCD（最大公约数）

辗转相除法

直接上代码：

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

复杂度：O(logn)

证明

若 a < b ，显然的gcd(a, b) = gcd(b, a) = gcd(b, a % b)
若 a > b ，可以设 a = q * b + r ，显然r = a % b
对于a,b, 的任意公约数d，显然的 d | a, d|q*b，那么显然d|a-q*b，也就是d|r。
由此得证。

更相减损术

对于正整数 a, b，有如下结论：(设 a > b)

gcd(a, b) = gcd(b, a-b) = gcd(a, a - b)
gcd(2a, 2b) = 2 * gcd(a, b)

可以由此求得最大公约数。
复杂度基本保持在O(logn)，不过有概率退化成O(n)。
它的主要用处是做高精gcd。

inline int get(int x, int y) {
    if(x == y) return x;
    if(x%2 == 0 && y%2 == 0) return 2 * get(x/2, y/2);
    if(x < y) swap(x, y);
    return get(y, x - y);
}

建议用while循环，否则炸栈内存。

多个数的最大公约数

可以开一个队列，每次取出两个数做gcd并把他们的gcd放入队列，直到队列中只剩一个数，那个数就是最大公约数。

最小公倍数

一般写为lcm(a,b)。

定理

设两个正整数a,b，有：

gcd(a,b) * lcm(a,b) = a * b

证明

设d = gcd(a, b),a_0 = a/d, b_0 = b/d，显然gcd(a_0, b_0) = 1, lcm(a_0, b_0) = a_0 * b_0，那么得:

lcm(a, b) = lcm(a_0 * d, b_0 * d) = lcm(a_0, b_0) * d = a_0 * b_0 * d = a * b / d

因为 d = gcd(a, b)，所以证明完成。

倍数法筛约数

就是考虑每个约数d的贡献。
这个方法的复杂度是 O(nlogn)，但是优点是可以求出所有的具体的约数且代码好写。

vector<int> factor[N];
void shai() {
    for(int i = 1; i <= n; ++i) 
        for(int j = 1; j * i <= n; ++j) 
            factor[i*j].push_back(i);
}

线性筛求约数个数

原理是线性筛质数和算数基本定理的结合。

int d[N], vis[N], num[N], prime[N], tot;//d[i]存i的u约数个数，num[i]存i的最小质因子的个数
void shai() {
    d[1] = 1;
    for(register int i = 2; i <= n; ++i) {
        //质数的约数个数为2,最小质因子的个数为1。
        if(vis[i] == 0) prime[++tot] = i, d[i] = 2, num[i] = 1;
        for(register int j = 1; j <= tot && i*prime[j] <= n; ++j) {
            vis[prime[j]*i] = 1;//最小质因子为prime[j]的合数
            if(i % prime[j] == 0) {//i的最小质因子为prime[j]
                num[i*prime[j]] = num[i] + 1;
                d[i*prime[j]] = d[i] / (num[i*prime[j]]) * (num[i*prime[j]] + 1);
                //相当于去掉原来的prime[j]，加入新的prime[j]。
                break;
            }
            else {
                num[i*prime[j]] = 1;
                d[i*prime[j]] = d[i]*2;//这个自己分析吧。
            }
        }
    }
}

复杂度不用过多分析，就是一个线性筛。
至于线性求约数和，暂时不讲。

过渡段

前面都是必须学会的基础知识，为后面做准备，后面的难度应该会更难一些。

欧拉函数

互质

对于两个正整数a，b，如果gcd(a,b) = 1，我们说这两个数互质。
对于多个数同样适用。

基本内容

##### 求法设$p_1,p_2,p_3, ... ,p_n$ 为N 的质因子，则： $$ \varphi(N) = N * \frac{p_1-1}{p_1} * \frac{p_2-1}{p_2} * ... * \frac{p_n-1}{p_n} $$ 证明：方法很多，可以用**容斥原理**证明，此处略过。所以我们只要分解质因数就可以求出欧拉函数的值。 ```cpp int phi(int n) { int ans = n; for(register int i = 2; i <= sqrt(n + 0.5); ++i) { if(n % i == 0) ans = ans / i * (i-1); while(n % i == 0) n /= i; } if(n > 1) ans = ans / n * (n-1); return ans; } ``` ### Eratosthenes筛求欧拉函数复杂度$O(nlogn)$，代码具短。大致思想就是用每个质数去筛欧拉函数。 ```cpp void shai() { for(register int i = 1; i <= n; ++i) phi[i] = i; for(register int i = 1; i <= n; ++i) { if(phi[i] == i) {//i为质数 for(register int j = i; j <= n; j += i) phi[j] = phi[j] / i * (i-1); } } } ``` ### 线性筛欧拉函数利用线性筛计算欧拉函数，具体原理代码中讲解。 ```cpp int phi[N], prime[N], tot, vis[N]; void shai() { phi[1] = 1;//1的欧拉函数是1 for(register int i = 2; i <= n; ++i) { if(vis[i] == 0) { prime[++tot] = i, phi[i] = i-1;//质数的欧拉函数是i-1 } for(register int j = 1; j <= tot && i * prime[j] <= n; ++j) { vis[i * prime[j]] = 1; if(i % prime[j] == 0) { //如果prime[j]是i的一个质因子 //f[i*prime[j]] = prime[j] * f[i],因为i中包括(i×prime[j])的所有质因子。 phi[prime[j] * i] = prime[j] * phi[i]; break; } else {//prime[j]与i互质 //根据它是积性函数：f(ab) = f(a) * f(b), [gcd(a, b) == 1] phi[prime[j] * i] = (prime[j] - 1) * phi[i]; } } } } ``` ## 积性函数如果 a,b 互质，并且有 $f(ab) = f(a) * f(b)$ ，那么就说函数为积性函数。暂时没有遇到过与他相关的题目。 ## 同余及其相关内容 ### 前置芝士若整数a,b除以正整数m的**余数**相等，则称 a,b 模 m **同余**，记为 $a \equiv b(mod$ $m)$ 。 #### 同余类 & 剩余系对于任意正整数 $a[0 <= a <= m-1]$，集合 $\{ a + km \}(k = 0, 1, 2, 3 ...)$ 模 m 同余，余数为 a ，则称该集合为一个模 m 的**同余类**。显然，m 的同余类一共有m个，它们构成 m 的**完全剩余系**。 ### 费马小定理若 p 是质数，则对于任意整数 a, 有 $a^p \equiv a(mod$ $p)$。也可以写做 $ a^{p-1} \equiv 1(mod$ $p)$。个人感觉证明就算了吧。 ### 欧拉定理若**正整数 a, n 互质**，则有 $ a^{\varphi(n)} \equiv a(mod$ $p)$，其中 $ \varphi(n) $ 是欧拉函数。 **推论** : 若正整数 a,n 互质，则有： $$ a^b \equiv a^{b mod \varphi(n)} (mod n)$$ 经常用于需要取模的乘方。证明略。 ### 二次探测定理若 $p$ 为**质数**且$x∈(0,p)$，则方程 $x^2≡1(mod$ $p)$ 的解为 $x = 1$, $ x = p−1$。 #### 证明移项后平方差展开后因为 $0 <= x <= p$，所以可以证明。 ### 裴蜀定理 #### 内容方程 $ax + by = c [a为正整数， b为正整数]$，有解的充要条件是 $gcd(a, b) | c$。注意其中 $c$ 必须大于等于 $gcd(a, b)$。放个[板子题](https://www.luogu.com.cn/problem/P4549) ```cpp #include <cstdio> using namespace std; inline int gcd(int x, int y) { return y ? gcd(y, x % y) : x; } int main() { int n, ans = 0, tmp = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &tmp); if(tmp < 0) tmp = -tmp; ans = gcd(ans, tmp); } printf("%d", ans); return 0; } ``` ### 扩展欧几里得求解**裴蜀定理**一组解的东西。通过求最大公约数的过程中求出它的一组特解。 ```cpp int exgcd(int a, int b, int &x, int &y){//取地址符号 if(b == 0) return x = 1, y = 0, a; int gcd = exgcd(b, a%b, x, y), d = x; x = y; y = d - y * a / b; return gcd; } ``` #### 证明在求最大公约数的最后一步，因为此时 $b = 0, a$ 就是最大公约数，所以显然的 $x = 1, y = 0$。因为 $gcd(a, b) = gcd(b, a$ % $b)$，所以设x, y 使其满足： $$ bx + (a - b[a/b])y = ay + b(x - [a/b]y) $$ 所以 $x = y, y = x - a/b * y$。 #### 通解设求出的特解为 $x_0, y_0$。通解为 $x = x_0 + k * b/gcd$, $ y = y_0 - k * a/gcd $，k 为整数。 ### 乘法逆元众所周知**同余不满足同除性**，所以数学家们弄出了**逆元**这个东西。通俗的来说就是如果整数 $b, m$ **互质**，如果有 $ b * x \equiv 1(mod$ $m) $，那么 $x$ 就是 $b$ 在 $mod$ $m$ 下的乘法逆元。求法：比较简单的是费马小定理逆元，但是要求模数为质数。还有欧拉定理求逆元和扩展欧几里得求逆元。 #### 线性求逆元建议直接背过： ```cpp Inv[ 1 ] = 1; for( int i = 2; i <= n; i++ ) Inv[ i ] = ( p - p / i ) * Inv[ p % i ] % p; ``` ## 卢卡斯定理（$Lucas$） ### 定理内容普通的求组合数一般提前预处理出来阶乘的逆元。但是当数据范围巨大的时候我们无法进行预处理，或者说给的mod很烂的时候，这时候我们就要用到**卢卡斯定理**来解决这个问题。公式： $Lucas(n, m, mod) = $ $C(n$ % mod$, m$ % $mod) * Lucas(n/mod, m/mod, mod)

其中Lucas(n, 0, mod) = 1
复杂度 O(p+log⁡p)∼O(log⁡n)，p为质数。
这就是Lucas定理的基本内容，证明放在代码后。

代码时刻

以洛谷板子题为例。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(int s = 0, char ch = getchar()) {
    while(!isdigit(ch)) { ch = getchar(); }
    while(isdigit(ch)) { s = s*10 + ch - '0'; ch = getchar(); }
    return s;
}
ll jie[100005], n, m, mod;
ll qpow(ll a, ll b, ll ans = 1) {//快速幂求逆元
    while(b) {
        if(b & 1) ans = ans * a % mod;
        b >>= 1, a = a*a % mod;
    }
    return ans;
}
ll suan(ll a, ll b) {//组合数公式
    if(a > b) return 0;
    return (jie[b] * qpow(jie[a], mod-2) % mod * qpow(jie[b-a], mod-2) % mod);
}
ll Lucas(int a, int b) {//递归实现Lucas
    if(!a) return 1;
    return suan(a%mod, b%mod) * Lucas(a/mod, b/mod) % mod;
}
int main() {
    int T = read();
    while(T--) {
        n = read(), m = read(); mod = read();
        jie[0] = 1;
        for(register int i = 1; i <= mod; ++i) jie[i] = jie[i-1] * i % mod;
        cout << Lucas(n, n + m) << '\n';
    }
    return 0;
}

恐怖证明

暂无，证明有亿点点难。

中国剩余定理（CRT）

基本内容

中国剩余定理主要用于求解模数互质的一组线性同余方程的解。

设m_1, m_2, m_3, .... , m_n为两两互质的整数，M = \prod \frac{n}{i=1}mi，Mi = M / m_i，t_i是线性同余方程 M_it_i \equiv 1(mod m_i) 的一个解。
对于任意的n个整数a_1, a_2, a_3, ... , a_n，方程组

\begin{cases} x\equiv a_1(modm_1) \\ x\equiv a_2(mod m_2)\\...\\x \equiv a_n(mod m_n) \end{cases}

有整数解，解为x = \sum_{i=1}^{n}a_iM_it_i
注意求出来的只是一组特解，方程的通解可以表示为x + kM(k为整数)。
复杂度：取决与逆元的求解。中国剩余定理为O(n)。

代码时刻

洛谷板子题

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20;
int n, a[N], m[N], Mi[N], M = 1, ans;
int exgcd(int a, int b, int &x, int &y) {
    if(b == 0) { return x = 1, y = 0, a; }
    int gcd = exgcd(b, a%b, x, y), c = x;
    x = y, y = c - (a/b)*y;
    return gcd;
}
signed main() {
    cin >> n;
    for(register int i = 1; i <= n; ++i) {
        cin >> m[i] >> a[i];
        M *= m[i];
    }
    for(register int i = 1; i <= n; ++i) {
        Mi[i] = M / m[i];
    }
    for(register int i = 1; i <= n; ++i) {
        int x, y;
        int gcd = exgcd(Mi[i], m[i], x, y);
        ans += a[i] * Mi[i] * (x < 0 ? x%m[i] + m[i] : x);
    }
    cout << ans%M << '\n';
    return 0;
}

感觉比较清晰。

基本证明

因为M_i = M/m_i，所以对于任意的k(k != i)，都有a_iM_it_i\equiv 0(mod m_k)，并且有a_iM_it_i \equiv a_i(mod m_i)，所以证明得出来的解是正确的。