数学芝士
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数学公式](https://blog.csdn.net/leviopku/article/details/81385790)
[Markdown](https://blog.csdn.net/jyfu2_12/article/details/79207643)
# 数论部分
## 质数及相关内容
### 简介
质数就是只能被1和它本身整除的数，它的个数大概为$n\div \ln n$个。
一些基本性质比如任何数都与1互质，除了2其他的偶数都不是质数等等，比较简单
### Eratosthenes筛素数
利用了一个质数的倍数一定不是质数的原理。
复杂度$O(nlognlogn)$。
```cpp
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$开始就可以。
```cpp
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)$。
大概原理就是用每个合数的最小质因子筛掉它。
```cpp
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的数，把它全部除尽。
```cpp
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（最大公约数）
#### 辗转相除法
直接上代码：
```cpp
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。
```cpp
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)$，但是优点是可以求出所有的具体的约数且代码好写。
```cpp
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);
}
```
### 线性筛求约数个数
原理是线性筛质数和算数基本定理的结合。
```cpp
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$，我们说这两个数互质。
对于多个数同样适用。
### 基本内容
$1-N$ 中与 $N$ 互质的数的个数叫做欧拉函数，写为 $\varphi(N)$。
##### 求法
设$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+logp)∼O(logn)$，p为质数。
这就是$Lucas$定理的基本内容，证明放在代码后。
### 代码时刻
以洛谷[板子题](https://www.luogu.com.cn/problem/P3807)为例。
```cpp
#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)$。
### 代码时刻
洛谷[板子题](https://www.luogu.com.cn/problem/P1495)
```cpp
#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)$，所以证明得出来的解是正确的。