基础数学专题复习

数学归纳法

格式:

证明当(n)的值为初值时的式子成立 (基础((basic)))
假设当(n = k)时原式成立，即有 : ....
则当(n = k + 1)时，论证式子恒成立 (归纳((induction)))

e.g. 1

数学归纳法证明等差数列存在(a_n = a_1 + (n - 1)d)

当(n = 2)时,(a_2 = a_1 + d),满足定义式: (a_n = a_{n - 1} + d)

假设(n = k)时,(a_k = a_1 + (k - 1)d)成立，则(n = k + 1)时,(a_{k + 1} = a_k + d = a_1 + (k - 1)d + d = a_1 + kd)

所以当(n geqslant 2)时,(a_n = a_1 + (n - 1)d) (qquad lacksquare)

e.g. 2

数学归纳法证明平面上的(n)条直线最多界定的区域个数(Ln = dfrac{n(n + 1)}{2} + 1 , n geqslant 0)

存在递推式:

(L_0 = 1)

(L_n = L_{n - 1} + n,n > 0)

当(n = 1)时，(L_1 = 1 + 1 = L_0 + 1),满足递推式

假设(n = k)时，(L_k = dfrac{k(k + 1)}{2} + 1)成立，则(n = k + 1)时，(L_{k + 1} = dfrac{k(k + 1)}{2} + 1 + (k + 1)=dfrac{(k + 1)(k + 2)}{2} + 1)

所以当(n geqslant 1)时，(Ln = dfrac{n(n + 1)}{2} + 1 , n geqslant 0) (qquad lacksquare)

Miller-Rabin

(Miller-Rabin) 素性检测

前置知识:

二次探测定理

若 (x ^ 2 equiv 1 (mod p)) 且 (x e 1) 且 (x e p - 1) 时， (p) 不是质数

(proof.)

(x ^ 2 equiv 1 (mod p)), (p mid (x + 1)(x - 1))

若 (p) 为素数，则 (p mid (x + 1)) 或 (p mid (x - 1))

解得 (x equiv 1 (mod p)) 或 (x equiv -1 (mod p))

若 (p) 为合数，则不一定成立， ((e.g. 25 mod 8))

((x + 1)) 和 ((x - 1)) 可能会各有一部分的 (p) 的因子

费马小定理

对于一个素数 (p)，有 (a ^ {p - 1} equiv 1 (mod p))

结合这两个理论，我们就能够开始我们的 (Miller-Rabin) 素性检测

可以证明，正确性大概是 (1 - 4 ^ {-k}) ，其中 (k) 为二次探测的次数

Pollard-Rho

不妨令 (n) 为我们需要质因数分解的数字

先用 (Miller-Rabin) 算法判断 (n) 是不是素数

然后考虑构建一个随机函数 (f(x) = x ^ 2 + c) ，其中 (c) 为随机常数

然后考虑随机函数值的差 (d) 与 (n) 的最大公约数，若 ((d, n) e 1) ，则找到了公约数，((d, n)) 就是 (n) 的一个约数

其中随机函数在 (mod n) 的意义下有可能出现环的情况，此时用到 (floyd) 判环

然后考虑倍增地求 ((d, n)) 的值，节约时间，但是考虑到判环的时候有可能多次错过，所以不用 (floyd) 判环而是直接用暴力判环即可

欧拉函数

定义

在学欧拉函数和莫比乌斯函数之前，先不妨设(n = {p_1}^{q_1} {p_2}^{q_2} cdots {p_k}^{q_k})

(varphi(n))是欧拉函数，表示 ([1, n]) 中与 (n) 互质的数的个数

(varphi(n) = n (1 - dfrac{1}{p_1})(1-dfrac{1}{p_2})cdots(1-dfrac{1}{p_k}))

基本公式

(sum limits_{d mid n} varphi(d) = n)

(Proof.)

[sumlimits_{d mid n}varphi(n) =sumlimits_{d mid n} varphi(dfrac{n}{d}) = sumlimits_{d mid n} sumlimits_{i = 1}^frac{n}{d}[gcd(dfrac{n}{d}, i) = 1]=sumlimits_{d mid n}sumlimits_{i = 1}^n[gcd(n, i) = d] = sumlimits_{i = 1}^nsumlimits_{d mid n}[gcd(n, i) = d] = sumlimits_{i = 1}^n1 = n ]

莫比乌斯函数

定义

(mu(n))是莫比乌斯函数，定义如下

(mu(n) = egin{cases}1 & n = 1 \ (-1)^k & max(q_1, cdots , q_k) = 1 \ 0 & otherwise end{cases})

基本公式

(sumlimits_{d mid n}mu(d)=[n = 1], sumlimits_{d mid n} d imes mu(dfrac{n}{d}) = varphi(n))

(varphi(n) = sumlimits_{i = 1}^n[gcd(i, n) = 1] = sumlimits_{i = 1}^n sumlimits_{d mid gcd(i, n)} mu(d) = sumlimits_{d mid n}mu(d)dfrac{n}{d} = sumlimits_{d mid n} dmu(dfrac{n}{d}))

莫比乌斯反演

若(F(n) = sumlimits_{d mid n} f(d)), 则 (f(n) = sumlimits_{d mid n}F(d) * mu(dfrac{n}{d}))

筛法

基本概念

积性函数

对于任意的两个正整数 (a ot b) 满足 (f(ab) = f(a) imes f(b))

完全积性函数

对于任意的两个正整数 (a), (b) 满足 (f(ab) = f(a) imes f(b))

狄利克雷卷积

(h(n) = sumlimits_{d mid n} f(d) g(dfrac{n}{d}))，称 (h(n)) 是 (f(n)) 和 (g(n)) 的狄利克雷卷积

一个定理

两个积性函数的狄利克雷卷积得到的函数仍然是积性函数

线性筛

线性筛，也称为欧拉筛

~~大家都会，就不整理了吧~~

杜教筛

计算一类特定积性函数前缀和的算法，例如(varphi(n))

[sumlimits_{i = 1}^n sumlimits_{d mid i} varphi(d) = sumlimits_{d = 1}^nvarphi(d) imes leftlfloordfrac{n}{d} ight floor = sumlimits{d = 1}^n sumlimits_{i = 1}^frac{n}{d}varphi(i) ]

[sum_{i=1}^{n} varphi(i)=sum_{i=1}^{n} sum_{d mid i} varphi(d)-sum_{d=2}^{n} sum_{i=1}^{leftlfloorfrac{n}{d} ight floor} varphi(i)=frac{n(n+1)}{2}-sum_{d=2}^{n} sum_{i=1}^{leftlfloorfrac{n}{d} ight floor} varphi(i) ]

所以可以从 (n) 递归到 (leftlfloorfrac{n}{i} ight floor)，众所周知总共只有 (sqrt{n}) 个结果，用记忆化搜索复杂度是 (O(n^frac{3}{4}))，如果预处理前 (n^frac{2}{3}) 的结果再记忆化复杂度就变成 (O(n^{frac{2}{3}})) 了

(e.g.) 给定一个 (n)，求 (sumlimits_{i = 1}^nmu(in)), 其中 (1 leqslant n leqslant 10^9)

(Solution:)

记(F(n, m) = sumlimits_{i = 1} ^ m mu(i n)), 则有:

(F(n, m) = sumlimits_{i = 1} ^ m mu(i n) = sumlimits_{i = 1}^m mu(i) mu(n) [gcd(i, n) = 1] = mu(n) sumlimits_{i = 1} ^ mmu(i)sumlimits_{d mid gcd(i, n)} mu(d))

(F(n, m) = mu(n) sumlimits_{d mid n}mu(d) sumlimits_{i = 1}^{leftlfloorfrac{m}{d} ight floor}mu(id) = mu(n) sumlimits_{d mid n}mu(d)F(d, {leftlfloordfrac{m}{d} ight floor}))

(n = 1)时用杜教筛求出，递归地去做，复杂度大概是 (O(n ^ {frac{2}{3}}))

欧几里得算法

(gcd(a, b) = gcd(b, a mod b))

(lcm(a, b) = dfrac{a imes b}{gcd(a, b)})

裴蜀定理

给定不全为 (0) 的整数 (a, b) , 存在整数 (x, y) 使得 (ax + by = gcd(a, b))

(e.g. CF510D Fox And Jumping)

给出 (n) 张卡片，分别有 (l_i) 和 (c_i)

在一条无限长的纸带上，你可以选择花 (c_i) 的钱来购买卡片 (i)，从此以后可以向左或向右跳 (l_i) 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 (-1)

(Solution.)

考虑整张纸带都能走, 那么我们就要使选定的卡片通过互相加减来变成 (1), 这样我们就能够走完整张纸带

依据裴蜀定理即得: (ax + by = gcd(a, b)) , 当 (a ot b) 时有 (gcd(a, b) = 1)

所以我们只要用 堆优化dijkstra 求解答案即可, 每次枚举 (l_1, l_2, cdots , l_n) 来转移到 (gcd(dis[u], l_i)) 即可

需要注意的是要用 unordered_map 来维护 dis[] 数组

扩展欧几里得算法

常用来求 (ax + by = gcd(a, b)) 的一组可行解

(ax_1 + by_1 = gcd(a, b))

(bx_2 + (a mod b) y_2 = gcd(b, a mod b))

(ecause gcd(a, b) = gcd(b, a mod b), herefore ax_1 + by_1 = bx_2 + (a mod b) y_2)

(ecause a mod b = a - {leftlfloordfrac{a}{b} ight floor} imes b, ax_1 + by_1 = bx_2 + (a - {leftlfloordfrac{a}{b} ight floor} imes b) y_2)

展开移项可得:

(x_1 = y_2, y_1 = x_2 - {leftlfloordfrac{a}{b} ight floor}y_2)

终止条件为 (x = 1, y = 0), 可以递归求解

类欧几里得算法

使用一个类似于辗转相除法的方法递归地做函数求和的过程

(e.g.) 给定 (a, b, c, n) 求解(sumlimits_{i = 0}^n{leftlfloordfrac{ai + b}{c} ight floor}), 其中 (n <= 10^9)

(Solution.)

核心思想是分类讨论然后将情况分开计算

定义 (F(a, b, c, n) = sumlimits_{i = 0}^n{leftlfloordfrac{ai + b}{c} ight floor})

(a geqslant c, b geqslant c)时，有:

(F(a, b, c, n) = sumlimits_{i = 0}^n{leftlfloordfrac{ai + b}{c} ight floor} = sumlimits_{i = 0}^n{leftlfloordfrac{({leftlfloorfrac{a}{c} ight floor} imes c + a mod c)i + ({leftlfloorfrac{b}{c} ight floor} imes c + b mod c)}{c} ight floor} = dfrac{n(n + 1)}{2} {leftlfloordfrac{a}{c} ight floor} + (n + 1){leftlfloordfrac{b}{c} ight floor} + f(a mod c, b mod c, c, n))

中国剩余定理

计算所有模数的积 (n) ;
对于第 (i) 个方程:

计算 (m_{i}=frac{n}{n_{i}})
计算 (m_{i}) 在模 (n_{i}) 意义下的逆元 (m_{i}^{-1})
计算 (c_{i}=m_{i} m_{i}^{-1}) (不要对 (n_{i}) 取模)

方程组的唯一解为: (quad a=sumlimits_{i=1}^{k} a_{i} c_{i} quad(mod n))

(Proof)

找们需要证明上面算法计算所得的 (a) 对于任意 (i=1,2, cdots, k) 满足 (a equiv a_{i}left(mod n_{i} ight) circ) 当 (i eq j) 时，有 (m_{j} equiv 0left(mod n_{i} ight)), 故 (c_{j} equiv m_{j} equiv 0left(mod n_{i} ight) cdot) 又有
(c_{i} equiv m_{i}left(m_{i}^{-1} mod n_{i} ight) equiv 1left(mod n_{i} ight)), 所以我们有 :

(egin{aligned} a & equiv sum_{j=1}^{k} a_{j} c_{j} & &left(mod n_{i} ight) \ & equiv a_{i} c_{i} & &left(mod n_{i} ight) \ & equiv a_{i} m_{i}left(m_{i}^{-1} mod n_{i} ight) & &left(mod n_{i} ight) \ & equiv a_{i} & &left(mod n_{i} ight) end{aligned})

即对于任意 (i=1,2, cdots, k), 上面算法得到的 (a) 总是满足 (a equiv a_{i}left(mod n_{i} ight)), 即证明了解同余方程组的算法的正确性。
因为我们没有对输入的 (a_{i}) 作特殊限制，所以任何一组输人 (left{a_{i} ight}) 都对应一个解 (a)
另外，若 (x eq y), 则总存在 (i) 使得 (x) 和 (y) 在模 (n_{i}) 下不同余。
故系数列表 (left{a_{i} ight}) 与解 (a) 之间是一一映射关系，方程组总是有唯一解。

扩展中国剩余定理

考虑两个同余方程的情况

[egin{cases}x equiv c_1 (mod m_1) \ x equiv c_2 (mod m_2) \ cdots \ x equiv c_r (mod m_r) end{cases}]

其中 (m_1, m_2, cdots, m_r) 存在 (m_{k1}) 和 (m_{k2}) 不互质

因为(CRT)要求模数互质，所以这个问题我们并不能用 (CRT) 来做

从简单的入手，我们考虑两个方程的情况

[egin{cases}x equiv c_1 (mod m_1) \ x equiv c_2 (mod m_2) \ end{cases}]

可以转化为:

(x = c_1 + m_1 k_1)

(x = c_2 + m_2 k_2)

所以 (c_1 + m_1 k_1 = c_2 + m_2 k_2)

移项得 (c_2 - c_1 = m_1 k_1 - m_2 k_2)

不妨用 ((m_1, m_2)) 来表示 (m_1, m_2) 的最大公约数

由裴蜀定理得 ((m_1, m_2) mid (c_2 - c_1))，否则方程无解

方程两边移项后同时除上 ((m_1, m_2))

有 (dfrac{m_1}{(m_1, m_2)}k_1 = dfrac{c_2 - c_1}{(m_1, m_2)} + dfrac{m_2}{(m_1, m_2)}k_2)

(dfrac{m_1}{(m_1, m_2)}k_1 equiv dfrac{c_2 - c_1}{(m_1, m_2)} (mod dfrac{m_2}{(m_1, m_2)}))

令 (inv(a, b)) 表示 (a) 在模 (b) 意义下的逆元

(k_1 equiv inv(dfrac{m_1}{(m_1, m_2)}, dfrac{m_2}{(m_1, m_2)}) imes dfrac{c_2 - c_1}{(m_1, m_2)} (mod dfrac{m_2}{(m_1, m_2)}))

展开得 : (k_1 = inv(dfrac{m_1}{(m_1, m_2)}, dfrac{m_2}{(m_1, m_2)}) imes dfrac{c_2 - c_1}{(m_1, m_2)} + y imes dfrac{m_2}{(m_1, m_2)})

又因为 (x = c_1 + m_1 k_1)

所以 (x = inv(dfrac{m_1}{(m_1, m_2)}, dfrac{m_2}{(m_1, m_2)}) dfrac{m_1}{(m_1, m_2)}(c_2 - c_1) + dfrac{m_1 m_2}{(m_1, m_2)}y + c_1)

(x equiv inv(dfrac{m_1}{(m_1, m_2)}, dfrac{m_2}{(m_1, m_2)}) dfrac{m_1}{(m_1, m_2)}(c_2 - c_1) + c_1 (mod dfrac{m_1 m_2}{(m_1, m_2)}))

这个式子可以理解为 (x equiv c (mod M))

其中 (c = ((inv(dfrac{m_1}{(m_1, m_2)}, dfrac{m_2}{(m_1, m_2)}) dfrac{(c_2 - c_1)}{(m_1, m_2)}) mod dfrac{m_2}{(m_1, m_2)}) imes m_1 + c_1)

(M = dfrac{m_1 m_2}{(m_1, m_2)})

扩展到多个方程的话就拿现有已考虑过的方程一个一个与未考虑的方程进行计算

费马小定理

对于(gcd(a, p) = 1), 且(p)为质数

[a ^ p equiv a (mod p) ]

(Proof 1.)

引理1. 若(n mid (a - b) , x > 0, gcd(x, n) = 1), 则(n mid x(a - b))

证明: 该结论显然

引理2. 对于集合(A = {1, cdots {p - 1}}), 则集合 ({ k in A, gcd(a, p) = 1, k imes a mod p }) 与 (A) 等价

证明: 对于互异的 (k) 来说, (k imes a) 在 (mod p) 意义下互异, 由引理1可得 (ecause p mid (k1 - k2),a > 0, gcd(a, p) = 1 herefore p mid a imes (k1 - k2))

由引理2可得 (ecause prod limits_{i = 1}^{p - 1}(i imes a) equiv prod limits_{i = 1}^{p - 1}i imes a ^ {p - 1}, prod limits_{i = 1}^{p - 1}i equiv prod limits_{i = 1}^{p - 1}i imes a ^ {p - 1} (mod p))

( herefore a^{p - 1} equiv 1 (mod p))

(Proof 2.)

引理1: 对于二项式系数(dbinom{p}{n}), 当(p)为质数且(n = 1 cdots {p - 1}, p mid dbinom{p}{n})

证明: 当(n = 1 cdots {p - 1}) 时, (ecause dbinom{p}{n} = dfrac{p!}{n!(n-p)!})， (p) 最后不会被分母消去, ( herefore n = 1 cdots {p - 1}, p mid dbinom{p}{n})

考虑 ((b + 1) ^ p) 展开

(egin{aligned} (b + 1) ^ p & = dbinom{p}{p} b ^ p + dbinom{p}{p - 1} b ^ {p - 1} + cdots + dbinom{p}{1} b ^ 1 + dbinom{p}{0} b ^ 0 \ & equiv dbinom{p}{p} b ^ p + dbinom{p}{0} b ^ 0 & (mod p) \ & equiv b ^ p + 1 &(mod p) \ & equiv (b - 1) ^ p + 1 + 1 &(mod p)\ & equiv (b - 2) ^ p + 1 + 1 + 1 &(mod p) \ & cdots \ & equiv egin{matrix}underbrace{1 + 1 + cdots + 1 + 1}\b + 1end{matrix} & (mod p) \ & equiv b + 1 & (mod p) end{aligned})

令(b = a - 1)，则有 (a ^ p equiv a (mod p))

欧拉定理

对于(a ot p)

[a ^ {varphi(p)} equiv 1 (mod p) ]

扩展欧拉定理

(a^b equiv egin{cases}a ^ {b mod varphi(p)}&gcd(a, p) = 1 \ a ^ b & gcd(a, p) e 1, b < varphi(p) & (mod p) \ a ^ {varphi(p) + b mod varphi(p)} & gcd(a, p) e 1, b geqslant varphi(p) end{cases})

威尔逊定理

[(p - 1)! equiv -1 (mod p) Longleftrightarrow P is a prime. ]

卢卡斯定理

[dbinom{n}{m} \% p = dbinom{n \% p}{m \% p} dbinom{ leftlfloordfrac{n}{p} ight floor }{ leftlfloordfrac{m}{p} ight floor } \% p ]

扩展卢卡斯定理

求 (dbinom{n}{m} mod p) 的值

不妨令 (x = dbinom{n}{m})

我们可以先对模数进行质因数分解:

(p = p_1^{k_1}p_2^{k_2}p_3^{k_3} cdots p_i^{k_i})

有同余方程:

(egin{cases}x equiv a_1 & (mod p_1^{k_1}) \ x equiv a_2 & (mod p_2^{k_2}) \ cdots \ x equiv a_i & (mod p_i^{k_i}) end{cases})

我们可以用 (CRT) 将上述同余方程合并起来，于是我们考虑怎么求 (a_i) 的值

考虑 (n! mod p_i^{k_i}) 的求法:

可以观察到有 (leftlfloordfrac{n}{p_i} ight floor! imes p_i imes 1 imes 2 imes cdots imes (p_i - 1) imes (p_i + 1) imes cdots n)

然后我们可以可以递归处理这个 (leftlfloordfrac{n}{p_i} ight floor!) ，至于 (p_i) 的话我们考虑提前把次数预处理出来，然后后面再乘即可

除此之外我们可以发现: 在 (mod p_i^{k_i}) 的意义下， (prodlimits_{i = 1}^{p_i^{k_i} - 1} i equiv prodlimits_{i = p_i^{k_i} + 1}^{2p_i^{k_i} - 1} i (mod p_i^{k_i}))

即只需要预处理一下 (prodlimits_{i = 1}^{p_i^{k_i} - 1} i)，然后快速幂一下就行了

组合数学

~~关于这个我觉得能够讲一年~~

基本定义

规定 (0! = 1)

[C(n, r) = dfrac{P(n, r)}{r!} = dfrac{n!}{(n - r)! r!} ]

[P(n, r) = dfrac{n!}{(n - r)!} ]

[Q(n, r) = dfrac{P(n, r)}{r} = dfrac{n!}{r(n - r)!} ]

基本定理

定理1 - 1 : 过(n)个有标志顶点的树的数目为(n ^ {n - 2}) ((Cayley)定理)

定理1 - 2 : 在 (n) 个不同元素中取 (r) 个作允许重复的组合，其组合数为 (dbinom{n + r - 1}{r})

定理1 - 3 : 从 (A = {1, 2, cdots , n}) 中取 (r) 个作不相邻的组合，其组合数为 (dbinom{n - r + 1}{r})

定理1 - 4 : 线性方程 (x_1 + x_2 + cdots + x_n = b) 的非负整数解个数为 (dbinom{n + b - 1}{b})

组合数奇偶性

(dbinom{n}{k} mod 2 equiv egin{cases} 1 & {n & k = k} \ 0 & otherwise end{cases})

二项式定理

[(x + y) ^ n = sumlimits_{i = 0}^ndbinom{n}{i} x^i y ^ {n - i} ]

`Pascal`公式

[dbinom{n}{m} = dbinom{n - 1}{m - 1} + dbinom{n - 1}{m} ]

图论中的组合数学公式

[sumlimits_{i = u}^v dbinom{i}{k} = dbinom{v + 1}{k + 1} - dbinom{u}{k + 1} ]

简单组合数学公式

[dbinom{m + n}{m} = dbinom{m + n}{n} iff dbinom{n}{r} = dbinom{n}{n - r} ]
[dbinom{n}{r} = dbinom{n - 1}{r} + dbinom{n - 1}{r - 1} ]
[dbinom{n + r + 1}{r} = dbinom{n + r}{r} + dbinom{n + r - 1}{r - 1} + cdots + dbinom{n}{0} ]
[dbinom{n}{l} dbinom{l}{r} = dbinom{n}{r} dbinom{n - r}{l - r}, l geqslant r ]
[(x + y) ^ m = dbinom{m}{0}x^m + dbinom{m}{1}x^{m - 1}y + cdots + dbinom{m}{m}y^m ]
[dbinom{m}{0} + dbinom{m}{1} + cdots + dbinom{m}{m} = 2^m ]
[dbinom{n}{0} - dbinom{n}{1} + dbinom{n}{2} -cdots pm dbinom{n}{n} = 0 ]
[dbinom{m + n}{r} = dbinom{m}{0} dbinom{n}{r} + dbinom{m}{1} dbinom{n}{r - 1} + cdots + dbinom{m}{r} dbinom{n}{0} ]
[dbinom{m + n}{m} = dbinom{m}{0} dbinom{n}{0} + dbinom{m}{1} dbinom{n}{1} + cdots + dbinom{m}{m} dbinom{n}{m}, m leqslant n ]
[dbinom{r}{r} + dbinom{r + 1}{r} + cdots + dbinom{n}{r} = dbinom{n + 1}{r + 1} ]
[dbinom{2n}{n} = dbinom{n}{0} ^ 2 + dbinom{n}{1} ^ 2 + cdots + dbinom{n}{n} ^ 2 ]
[P^n_r = n P^{n - 1}_{r - 1} = (n - r + 1) P^n_{r - 1} = dfrac{n}{n - r}P^{n - 1}_r ]
[P^{n + 1}_r = P^n_r + rP^n_{r - 1} = r! + r(P^n_{r - 1} + P^{n - 1}_{r - 1} + cdots + P^r_{r - 1}) ]
[sumlimits_{k = 1}^nkdbinom{n}{k} = n 2 ^ {n - 1} ]
[dbinom{n + 1}{2} + 2dbinom{n + 1}{3} = sumlimits_{k = 1}^n k ^ 2 ]
[dbinom{n}{r} = dfrac{n}{r} dbinom{n - 1}{r - 1}, 1 leqslant r leqslant n ]
[dbinom{n}{r} = dfrac{n - r + 1}{r} dbinom{n}{r - 1}, 1 leqslant r leqslant n ]
[dbinom{n}{r} = dfrac{n}{n - r} dbinom{n - 1}{r}, 0 leqslant r leqslant n ]
[dbinom{m}{0}dbinom{m}{n} + dbinom{m}{1} dbinom{m - 1}{n - 1} + cdots + dbinom{m}{n} dbinom{m - n}{0} = 2 ^ n dbinom{m}{n} ]
[dbinom{n}{0} 2 ^ n + dbinom{n}{2} 2 ^ {n - 2} + cdots + dbinom{n}{q} 2 ^ {n - 1} = dfrac{3 ^ n + 1}{2}, q = 2[dfrac{n}{2}] ]

原根和阶

阶

若 (a ot m) ，使 (a^l equiv 1 (mod m)) 成立的最小的 (l) ，称为 (a) 关于模 (m) 的阶，记为 (ord_ma)

原根

若 (g ot m) ，若 (ord_mg = varphi(m))，则称 (g) 为 (m) 的一原根

也可表述为 : (g) 为 (m) 的原根当且仅当集合 ({ g, g^2, cdots , g^{varphi(m)}}) 构成模 (m) 的一个既约剩余系

BSGS

可用于求解 (a ot p) 时，满足 (a ^ x equiv b (mod p)) 的最小的 (x)

我们不妨令 (x = A imes leftlceilsqrt{p} ight ceil - B)

则有 (a ^ {A imes leftlceilsqrt{p} ight ceil - B} equiv b (mod p))

移项得 (a ^ {A imes leftlceilsqrt{p} ight ceil} equiv b imes a ^ B (mod p))

其中 (1 le A, B le sqrt{p}), 于是我们可以枚举 (B) 的取值，然后把关于模 (p) 意义下的余数用 map 存下来 ( 或者用Hash_Table更好 )

然后枚举 (A) ，计算 (a ^ {A imes leftlceilsqrt{p} ight ceil}) 在模 (p) 的意义下的余数，然后再看 map 中有没有对应的 (B)，如果存在，输出 (A imes leftlceilsqrt{p} ight ceil - B) 即可

当然该方法能够求解所有满足条件的 (x)

EXBSGS

考虑 (gcd(a, p) > 1) 的情况，此时不满足 (bsgs) 中的互质条件，考虑怎样转换题目

我们考虑将原来的式子进行转换

(a ^ x equiv b (mod p) Rightarrow a ^ x + p imes k = b)

不妨令 (gcd(a, p) = d_0) ，则有 (dfrac{a ^ x}{d_0} + dfrac{k}{d_0} imes p = dfrac{b}{d_0})

然后我们可以继续考虑 (d_i = gcd(frac{b}{prodlimits_{i = 0}^{i - 1}d_{i}}, a))

不妨令 (D = prodlimits_{i = 0}^{i}d_i)

最后将式子转化成了 (dfrac{a ^ x}{D} + dfrac{k}{D} imes p = dfrac{b}{D})

即 (dfrac{a ^ x}{D} equiv dfrac{b}{D} (mod dfrac{p}{D} ))

若 (D mid p) ，则该方程无解

此时即可把这个问题转化为 (BSGS) 求解

一些概念及定义

完全剩余系

指 ({ 0, 1, cdots, p - 2, p - 1 }) 构成的集合称为模 (p) 的一个完全剩余系

既约剩余系

模 (p) 的一个既约剩余系指的是完全剩余系中与 (p) 互质的元素组成的集合