常见的数学符号
- $x|y$ ：表示 x 整除 y ，即 $y\%x==0$ ，也即 x 是 y 的因数。
- $x\ mod\ y$ ：表示 $x\%y$，$3\%2=1$
- $gcd$ ：最大公约数， $gcd(5,10)=5$ ，有时直接用 $(x,y)$ 表示
- $lcm$ ：最小公倍数， $lcm(6,8)=24$ ，有时直接用[x,y]表示
- $\bot$ ：互质， $x\bot y$ 即 $gcd(x,y)=1$
- $a \equiv b\pmod{m}$ ：同余关系， $ a \bmod m= b \bmod m$，也可以写成 $a+mx=b$
- $\sum ^{n}_{i=1}$ ：求从1到n的和，$\sum_{d|n}1$ 表示求约数个数， $\sum_{d|n}d$ 表示求约数和
- $\lfloor \frac{x}{y}\rfloor$ ：下取整，$\lfloor \frac{5}{3}\rfloor=1$
- $\lceil \frac{x}{y} \rceil$ ：上取整， $\lceil \frac{5}{3} \rceil=2$
- $[ n = 1 ]$ ：如果方括号内的条件满足则为1，不满足则为0。
- $\binom{n}{k}$：组合数 $C_n^k$ ，计算公式为 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ （注意两者顺序）
同余的性质
同余关系是等价关系满足性质
- 自反性：$a \equiv a\pmod{m} $
- 对称性：$b\equiv a \pmod m \iff a \equiv b \pmod m$
- 传递性：$a \equiv b \pmod m,b \equiv c \pmod m \Longrightarrow a\equiv c \pmod m$
若$a \equiv c \pmod m,b\equiv d \pmod m$ ，则其满足线性运算
- $a\pm b\equiv c \pm d \pmod m$
- $a\times b\equiv c\times d \pmod m$
- 若$k\times a\equiv k\times b\pmod m$，且k，m互质，则$a\equiv b\pmod m$
若$a \equiv b\pmod{m}$，k为正整数，则
$$ ak \equiv bk \pmod {mk} $$
若$d|a,d|b$ ,d|m，则
$$ \dfrac{a}{d}\equiv \dfrac{b}{d} \left(mod\ \ \dfrac{m}{d}\right) $$
若$d|m$，则
$$ a \equiv b \pmod d $$
一个很常见的恒等式（要求p为一个质数）
$$ \left( 1+x\right)^{p}\equiv 1+x^{p} \pmod p $$
我们利用二项式来进行简单的证明
$$ \left(1+x\right)^{p}=\binom{p}{0}+\binom{p}{1}x^1+\binom{p}{2}x^2+\cdots+\binom{p}{p}x^p $$
其中$\binom{p}{i}$在 $0<i<p$ 时必然是一个整数，且分子的质数 p 不会被任何数约去，故
$$ \binom{p}{1}\equiv\binom{p}{2}\equiv\cdots\equiv\binom{p}{p-1}\equiv0\pmod p $$
该恒等式即得证
快速幂
快速幂板子
int ksm(int a, int b, int m) {
a %= m;
int res = 1;
while (b) {
if (b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}$$ 17^{13}=17^{\left( 1101\right)_2}=17^{\left( 1000\right)_2+\left( 100\right)_2+\left( 1\right)_2}=17^{\left( 1000\right)_2}*17^{\left( 100\right)_2}*17^{\left( 00\right)_2}*17^{\left( 1\right)_2} $$
$$ 17=17=17^{\left( 1\right)_2} $$
$$ 17*17=289=17^{\left( 10\right)_2} $$
$$ 289*289=83521=17^{\left( 100\right)_2} $$
$$ 83521*83521=6975757441=17^{\left( 1000\right)_2} $$
根据以上数据，我们可以得到，成功将13次运算在4次运算内解决
$$ 17^{13}=17*83251*6975757441 $$
我们将a的幂（即b）二进制进行遍历，如果这一位是1，我们需要乘上对应的 $a^{2^{i}}$
a = a * a % m 这一步就是在计算 $a^{2^{i}}$ ，而我们需要计算多少个a就取决于b的二进制有多少位，于是这个算法的时间复杂度就是 $log$ 级别
题目链接：
快速幂求逆元
幺元：也叫单位元，一般用 e 表示，满足$ex=x$
逆元：一般用inv()表示，一个元素与它的逆元满足$a*inv(a)=e$
对于同余关系，其幺元为1，因为$1*x\equiv x\pmod m$
我们可以找到根据费马小定理找到a的逆元（即 $ax\equiv 1\pmod m$ 的解）
并解同余方程 $ax\equiv b \pmod m$ 的解，等式两边同时乘inv(a)，方程变为
$$ inv(a)*a*x\equiv inv(a)*b\pmod p $$
$$ e*x\equiv inv(a)*b\pmod p $$
$$ x\equiv inv(a)*b\pmod p $$
求模运算下的逆元可以根据费马小定理求出inv(a)
首先介绍费马小定理（证明见费马小定理）
$$ a^{p}\equiv a\pmod p $$
或
$$ a^{p-1}\equiv1\pmod p $$
其中p为质数
将左边的式子分开写我们能得到
$$ a*a^{p-2}\equiv 1\pmod p $$
再来看逆元的形式
$$ a*inv(a)\equiv 1\pmod p $$
两式对比可以得到
$$ inv(a)\equiv a^{p-2}\pmod p $$
代入 $x\equiv inv(a)*b$ 即可得到方程 $ax\equiv b \pmod m$ 的解，这个解可以用快速幂来解决
int inva=ksm(a, p - 2);GCD LCM
唯一分解定理
$$ N=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\cdots p_{n}^{k_{n}} $$
其中p均为质数，任何一个数都能分解成若干个质数的乘积，两个数的gcd即为每个质数阶的min，lcm即为每个质数阶的max
$$ gcd(a,b)=p_{1}^{min(k_{a1},k_{b1})}p_{2}^{min(k_{a2},k_{b2})}\cdots p_{n}^{min(k_{an},k_{bn})} $$
$$ lcm(a,b)=p_{1}^{max(k_{a1},k_{b1})}p_{2}^{max(k_{a2},k_{b2})}\cdots p_{n}^{max(k_{an},k_{bn})} $$
根据唯一分解定理可以得到以下性质
$$ (a_{1},a_{2},a_{3}\cdots a_{n})=(\lvert a_{1}\rvert ,\lvert a_{2}\rvert ,\lvert a_{3}\rvert \cdots \lvert a_{n}\rvert) $$
$$ (a,b)=(b,a) $$
$$ (a,a)=(a,0)=a $$
$$ (a^{n},b^{n})=\left(a,b\right)^{n} $$
$$ (a,b)[a,b]=\lvert ab\rvert $$
$$ \frac{\left(a,b,c\right)^{2}}{(a,b)(b,c)(c,d)}=\frac{\left[a,b,c\right]^{2}}{[a,b][b,c][c,d]} $$
练习题
辗转相除法
根据以下两条性质，我们可以得到辗转相除法代码
$gcd(a,b)=gcd(b,a\%b)=gcd(a\%b,b\%(a\%b))$ 或 $gcd(bq+r,a)=gcd(a,r)$
$gcd(a,0)=a$
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}在cpp中可以使用 __gcd(a,b) 得到最大公约数
练习题
质数筛
详见积性函数大杂烩
模板
埃筛
vector<bool> isp(N,true);
vector<int> primes;
void eratosthenes(int n){
isp[0] = isp[1] = false;
for(int i=2;i<=n;i++){
if(isp[i]){
primes.push_back(i);
for(int j=2*i;i<n;j+=i){
isp[j]=false;
}
}
}
}欧拉筛
vector<bool> isp(N,true);
vector<int> primes;
void get_prime(int n){
isp[0] = isp[1] = false;
for(int i=2;i<=n;i++){
if(isp[i])primes.push_back(i);
for(auto p:primes){
if(p*i>n)break;
isp[p*i]=false;
if(i%p==0){
break;
}
}
}
}练习题
卢卡斯定理
定义内容
卢卡斯定理（Lucas' theorem）是一个组合数学中的定理，它描述了模素数 $p$ 的二项式系数。具体来说，若 $n$ 和 $k$ 是非负整数，并且 $p$ 是素数，那么二项式系数 $\binom{n}{k}$ 模 $p$ 的值可以通过以下公式计算：
$$ \binom{n}{k} \equiv \prod_{i=0}^m \binom{n_i}{k_i} \pmod{p} $$
其中，$n_i$ 和 $k_i$ 是 $n$ 和 $k$ 在基数 $p$ 下的数字表示，即：
$$ n = n_0 + n_1 p + n_2 p^2 + \cdots + n_m p^m $$
$$ k = k_0 + k_1 p + k_2 p^2 + \cdots + k_m p^m $$
且 $0 \leq n_i, k_i < p$。
比赛中常用以下形式
$$ C_a^b \equiv C_{\lfloor\frac{a}{p}\rfloor}^{\lfloor \frac{b}{p} \rfloor} \cdot C_{a\%p}^ {b\%p} \pmod p $$
证明
根据二项式展开
$$ \left(1+x\right)^{a}=\binom{a}{0}x^{0}+\binom{a}{1}x^{1}+\binom{a}{2}x^{2}+\binom{a}{3}x^{3}+\cdots+\binom{a}{n}x^{a} $$
则我们要求的 $\binom{a}{b}$ 就是 $x^{b}$ 项所对应的次数，下面我们将 $a$ 进行一下变形
$$ \left(1+x\right)^a=\left(1+x\right)^{a_0+a_1*p} =\left(1+x\right)^{a_0}*\left(1+x\right)^{a_1*p} $$
其中 $a_0=a\%p ,a_1=a/p$
根据前面证明的式子
$$ \left( 1+x\right)^{p}\equiv 1+x^{p} \pmod p $$
我们可以得到
$$ \left(1+x\right)^{a}\equiv\left(1+x\right)^{a_0}*\left(1+x^{p}\right)^{a_1}\pmod p $$
将b变为 $b_0+b_1*p$ ，则不难看出 $x^{b_0}$ 仅能由 $\left(1+x\right)^{a_0} $贡献得到，$x^{b_1*p}$ 仅能由 $\left(1+x\right)^{a_1*p}$ 贡献得到
那么我们将两项对应系数分别展开，并选择能 $b_0,b_1*p$ 的两项相乘，与左式 $\left(1+x\right)^{a}$ 展开的 $x^{b}$ 项对比，即可得到
$$ \binom{a}{b}\equiv \binom{a_0}{b_0}*\binom{a_1}{b_1}\equiv\binom{a\%p}{b\%p} \binom{\lfloor a/p\rfloor}{\lfloor b/p\rfloor}\pmod p $$
模板
const int N = 100010;
#define int long long
int a[N];
int p;
int pow(int a,int b,int p){
int ans=1;
while(b){
if(b&1)ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
int C(int n,int m){
if(m>n)return 0;
return ((a[n]*pow(a[m],p-2,p))%p*pow(a[n-m],p-2,p)%p);
}
int Lucas(int n,int m){
if(!m)return 1;
return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
void solve(){
int n,m;
cin>>n>>m>>p;
a[0]=1;
for(int i=1;i<=p;i++)a[i]=(a[i-1]*i)%p;
cout<<Lucas(n+m,n)<<endl;
}练习题
前排(bushi