常见的数学符号

1. $x|y$ ：表示 x 整除 y ，即 $y\%x==0$ ，也即 x 是 y 的因数。
2. $x\ mod\ y$ ：表示 $x\%y$，$3\%2=1$
3. $gcd$ ：最大公约数， $gcd(5,10)=5$ ，有时直接用 $(x,y)$ 表示
4. $lcm$ ：最小公倍数， $lcm(6,8)=24$ ，有时直接用[x,y]表示
5. $\bot$ ：互质， $x\bot y$ 即 $gcd(x,y)=1$
6. $a \equiv b\pmod{m}$ ：同余关系， $a \bmod m= b \bmod m$，也可以写成 $a+mx=b$
7. $\sum ^{n}_{i=1}$ ：求从1到n的和，$\sum_{d|n}1$ 表示求约数个数， $\sum_{d|n}d$ 表示求约数和
8. $\lfloor \frac{x}{y}\rfloor$ ：下取整，$\lfloor \frac{5}{3}\rfloor=1$
9. $\lceil \frac{x}{y} \rceil$ ：上取整， $\lceil \frac{5}{3} \rceil=2$
10. $[ n = 1 ]$ ：如果方括号内的条件满足则为1，不满足则为0。
11. $\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);

练习题 求组合数——Y佬专门造数据提供的题目

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;
            }
        }
    }
}

练习题

输出第k小的素数

卢卡斯定理

定义内容

卢卡斯定理（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;
}

练习题

卢卡斯定理