数学
数论
唯一分解定理
定理
对于任意正整数 \(a\)，均有：
\[a=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n} \]其中 \(p_1,p_2\cdots p_n\)均为质数。
约数和公式
对于任意正整数 \(a=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}\)，其约数和 \(k\) 为
\[k=({p_1}^0+{p_1}^1+ \cdots {p_1}^{k_1})({p_2}^0+{p_2}^1+\cdots+{p_2}^{k_2})\cdots({p_n}^0+{p_n}^1+\cdots+{p_n}^{k_n}) \]裴蜀定理
采用常用的形式描述：
对于方程 \(ax+by=c\)，当且仅当 \(\gcd(a,b)\mid c\) 时，方程有整数解。
扩展欧几里德算法
- 解方程 \(ax+by=gcd(a,b)\)
运用以下代码求出一个特解 \(x_0\).
void exgcd(int a, int b, int &x, int &y) {
if (b == 0)
return x = 1, y = 0, void();
exgcd(b, a % b, y, x);
y = y - a / b * x;
}
则方程最小正整数解 \(x=(x_0\%b+b)\%b\)。
- 解方程 \(ax+by=c\)
记 \(g=gcd(a,b)\)，则：
a. 若 \(g\nmid c\)，原方程无整数解。
b. 若 \(g\nmid c\)，先转化为问题1，求方程 \(ax+by=gcd(a,b)\) 的一个特解 \(x_0\)，记 \(k=\frac{b}{g}\) ，那么原方程的一个特解 \(x_1\) 就是 \(x_1=k\times x_0\).
方程的最小正整数解就是 \(x=(x_1\%k+k)\%k\).
逆元
求 \(a^{-1}\pmod p\)
费马小定理求逆元
当 \(p\) 为质数时，我们可以用费马小定理求 \(a^{-1}=a^{p-2}\).
代码：
int qpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1)
ans = ans * x % p;
x = x * x % p;
y >>= 1;
}
return ans;
}
扩展欧几里德定理求逆元
当 \(\gcd(a,b)=1\)时，我们可以通过调用 \(exgcd(a,p,x,y)\) 求出 \(a^{-1}=x\)。
代码：
void exgcd(int a, int b, int &x, int &y) {
if (b == 0)
return x = 1, y = 0, void();
exgcd(b, a % b, y, x);
y -= a / b * x;
}
线性递推求逆元
当需要线性递推求逆元时，采用以下代码求逆元。
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}
线性同余方程
形如 $ ax\equiv b\pmod n $ 的方程称为线性同余方程
方程的解是 $ x\equiv ba ^ {- 1} \pmod n.$
欧拉函数
\(\varphi(i)\) 表示的是小于等于 \(n\) 和 \(n\) 互质的数的个数。
求单个数欧拉函数的求法:
int solve(int n) {
int ans = n;
for (int i = 2; i * i <= n; 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;
}
筛法求欧拉函数:
vector<int>v;
int phi[N];
bitset<N>pri;
int n;
void get_p() {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if(!pri[i]) {
v.push_back(i);
phi[i] = i - 1;
}
for(int j = 0; j < (int)v.size() && v[j] * i <= n; j++) {
pri[i * v[j]] = true;
if(i % v[j] == 0) {
phi[i * v[j]] = phi[i] * v[j];
break;
}
phi[i * v[j]] = phi[i] * phi[v[j]];
}
}
}
欧拉定理
欧拉定理
若 \(gcd(a, m) = 1\) ，则 \(a^{\varphi(m)} \equiv 1 \pmod{m}\)
扩展欧拉定理
$ a^b\equiv \begin{cases} a^{b\bmod\varphi(p)},,&\gcd(a,,p)=1\ a^b,&\gcd(a,,p)\ne1,,b<\varphi(p)\ a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,,p)\ne1,,b\ge\varphi(p) \end{cases} \pmod p $
中国剩余定理
中国剩余定理
中国剩余定可求解如下形式的一元线性同余方程组（其中 \(n_1, n_2, \cdots, n_k\) 两两互质）
\[\begin{cases} x &\equiv a_1 \pmod {n_1} \\ x &\equiv a_2 \pmod {n_2} \\ &\vdots \\ x &\equiv a_k \pmod {n_k} \\ \end{cases} \]具体解法：
-
计算所有模数的积 \(n\)
-
对于第 \(i\) 个方程：
a. 计算 \(m_i=\frac{n}{n_i}\)
b.计算 \(m_i\) 在模 \(n_i\) 意义下的逆元 \(m^{-1}\)
c.计算 \(c_i=m_im_i^{-1}\)(不要对 \(n_i\) 取模）
-
方程组在模 \(n\) 意义下的唯一解为 \(x=\sum^k_{i=1}a_ic_i \pmod n\)
实现：
int CRT(int m[], int r[]) {
int M = 1, ans = 0;
for(int i = 1; i <= n; i++)
M *= m[i];
for(int i = 1; i <= n; i++) {
int c = M / m[i], x, y;
exgcd(c, m[i], x, y);
ans = (ans + r[i] * c * x % M + M) % M;
}
return (ans + M) % M;
}
扩展中国剩余定理
当方程组中每一个模数 \(n_i\) 不互质时，需要用到中国剩余定理。
考虑两个方程的情况。
设两个方程分别是 \(x\equiv a_1 \pmod {m_1}\)，\(x\equiv a_2 \pmod {m_2}\)
将它们转化为不定方程： \(x=m_1p+a_1=m_2q+a_2\) ，其中 \(p, q\) 是整数，则有 \(m_1p-m_2q=a_2-a_1\) 。
由 裴蜀定理，当 \(a_2-a_1\) 不能被 \(\gcd(m_1,m_2)\) 整除时，无解
其他情况下，可以通过 扩展欧几里得算法 解出来一组可行解 \((p, q)\) ；
则原来的两方程组成的模方程组的解为 \(x\equiv b\pmod M\) ，其中 \(b=m_1p+a_1\) ， \(M=\text{lcm}(m_1, m_2)\) 。
然后多个方程时两两合并即可。
代码：
int md[N], rem[N];//存模数和余数
int qmul(int a, int b, int p) {//龟速乘
int ans = 0;
while (b) {
if (b & 1)
ans = (ans + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ans;
}
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int gcd = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return gcd;
}
signed main() {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> md[i] >> rem[i];
int X = rem[1];//存解
int LCM = md[1];//存前 i - 1 个方程模数的lcm
for(int i = 2; i <= n; i++) {
int p = md[i];
int res = ((rem[i] - X) % p + p) % p;
int x, y, Gcd = exgcd(LCM, p, x, y);
if(res % Gcd) {//判断无解
puts("-1");
return 0;
}
x = qmul(x, res / Gcd, p);
X += x * LCM;
LCM = p / Gcd * LCM;
X = (X % LCM + LCM) % LCM;
}
cout << X << "\n";
return 0;
}
排列组合
排列组合三大方法
插板法
不允许为空的插板
有 \(n\) 个元素，分为 \(k\) 组，每组保证有一个元素，问方案数。
公式：
允许为空的插板
有 \(n\) 个元素，分为 \(k\) 组，每组允许为空，问方案数。
公式：
插空法
若有 \(n\) 个 \(A\) 类物品和 \(m\) 个 \(B\) 类物品，将其插入一段长度为 \(n+m\) 的序列，且要求 \(B\) 类物品不能相邻，求方案数。
公式：
\[A^n_n\times A^m_{n+1} \]先计算 \(A\) 类物品的排列情况：\(A_n^n\)，此时我们认为序列里共有 \(n+1\) 个空，此时 \(B\) 类物品的情况就是 \(A_{n+1}^m\) 了。最终答案就是二者相乘。
捆绑法
若有 \(n\) 个 \(A\) 类物品和 \(m\) 个 \(B\) 类物品，将其插入一段长度为 \(n+m\) 的序列，且要求 \(B\) 类物品必须相邻，求方案数。
公式：
\[A_{n+1}^{n+1}\times A^m_m \]将所有 \(B\) 类物品看为一个物品，此时的排列情况是 \(A_{n+1}^{n+1}\)，再考虑 \(B\) 类物品内部的情况，方案数是 \(A_{m}^{m}\)，最终答案就是二者相乘。
二项式定理
\[(a+b)^n=\sum^n_{i=0} {n\choose i} a^{n-i}b^i \]二项式反演
形式1
记 \(f_n\) 为恰好使用 \(n\) 个不同元素形成特定结构的方案数， \(g_n\) 为从 \(n\) 个不同元素中选出 \(i\geq 0\) 个元素形成特定结构的方案数。
若已知 \(f_n\) 求 \(g_n\)，则显然：
\[g_n=\sum^n_{i=0}{n\choose i}f_i \]若已知 \(g_n\) 求 \(f_n\)，则有：
\[f_n=\sum^n_{i=0}{n\choose i}(-1)^{n-i}g_i \]形式2
记 \(f_k\) 为恰好使用 \(k\) 个不同元素形成特定结构的方案数， \(g_k\) 为从 \(n\) 个不同元素中选出 \(i\geq k\) 个元素形成特定结构的方案数。
若已知 \(f_k\) 求 \(g_k\)，则显然：
\[g_k=\sum^n_{i=k}{i\choose k}f_i \]若已知 \(g_k\) 求 \(f_k\)，则有：
\[f_k=\sum^n_{i=k}{i\choose k}(-1)^{n-k}g_k \]或许可以把它理解成一种容斥的变形？
二项式反演的主要用途是在把所求答案是恰好，但至少/不多于这样的答案好求时可以转化答案进行计算。
卢卡斯定理
若 \(p\) 为质数，对于 \(n,m\) 很大， \(p\) 很小时的公式：
\[{n\choose m}={{\lfloor n/p \rfloor }\choose {\lfloor m/p \rfloor}}\cdot{{n\mod p}\choose{m\mod p}} \]代码：
int C(int n, int m) {
if(m > n)
return 0;
return fac[n] * qpow(fac[m] * fac[n - m] % p, p - 2) % p;
}
int Lucas(int n, int m) {
if(m > n)
return 0;
if(!m)
return 1;
return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}
错排问题
错位排列是没有任何元素出现在其有序位置的排列。即，对于 \(1\sim n\) 的排列 \(P\) ，如果满足 \(P_i\neq i\) ，则称 \(P\) 是 \(n\) 的错位排列。
递推公式：
\(D_1=0,\ D_2=1,\ D_3=2;\)
\(D_n=(n-1)(D_{n-1}+D_{n-2})\)
常用公式
\[ \binom{n}{m}=\binom{n}{n-m} \]\[\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1} \]\[ \binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1} \]\[\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n \]\[ \sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0] \]\[ \sum_{i=0}^m \binom{n}{i}\binom{m}{m-i} = \binom{m+n}{m}\ \ \ (n \geq m) \]\[\sum_{i=0}^ni\binom{n}{i}=n2^{n-1} \]\[ \sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2} \]\[\sum_{i=0}^n{l\choose k}={{n+1}\choose k+1} \]\[\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k} \]\[ \sum_{i=0}^n\binom{n-i}{i}=F_{n+1} \]其中 \(F\) 是斐波那契数列。
\[ \sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2} \]数学方法
高斯消元
一般使用高斯-约旦消元法
// Gauss_Jordan 模板
#include <bits/stdc++.h>
#define N 105
using namespace std;
const double eps = 1e-6;
int n;
double a[N][N];
bool gauss_jordan() {
for (int i = 1; i <= n; i++) {
int r = i;
for (int k = i; k <= n; k++)
if (fabs(a[k][i]) > eps) {
r = k;
break;
}
if (r != i)
swap(a[r], a[i]);
if (fabs(a[i][i]) < eps)
return false;
for (int k = 1; k <= n; k++) {
if (k == i)
continue;
double t = a[k][i] / a[i][i];
for (int j = i; j <= n + 1; j++)
a[k][j] -= t * a[i][j];
}
}
for (int i = 1; i <= n; i++)
a[i][n + 1] /= a[i][i];
return true;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n + 1; j++)
scanf("%lf", &a[i][j]);
if (gauss_jordan())
for (int i = 1; i <= n; i++)
printf("%.2lf\n", a[i][n + 1]);
else
puts("No Solution");
return 0;
}
BSGS
给定一个质数 \(p\)，以及一个整数 \(a\)，一个整数 \(b\)，现在要求你计算一个最小的非负整数 \(l\)，满足 \(a^l \equiv b \pmod p\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int p, a, b;
int BSGS() {
unordered_map<int, int>mp;
a %= p;
b %= p;
int s = ceil(sqrt(p));
int t = b;
mp[b] = 0;
for (int i = 1; i <= s; i++) {
t = t * a % p;
mp[t] = i;
}
int x = 1;
for (int i = 1; i <= s; i++)
x = x * a % p;
t = 1;
for (int i = 1; i <= s; i++) {
t = t * x % p;
if (mp.count(t))
return i * s - mp[t];
}
return -1;
}
signed main() {
cin >> p >> a >> b;
int tmp = BSGS();
if(~tmp)
cout << tmp << "\n";
else
puts("no solution");
return 0;
}