运用乘法逆元解决模意义下的除法问题,将其转换为模意义下的乘法,了解多种求乘法逆元的思路

乘法逆元介绍


  • 引入

    1、对于模意义下的运算,例如我们知道(a + b) % p = (a % p) + (b % p)或者(a * b) % p = (a % p) * (b % p)成立,但是对于模意义下的除法不成立(a / b) % p != (a % p) / (b % p)。不过,我们可以把模意义的除法转换成模意义的乘法
    2、举例探讨:(7 / 2) % 5 中,把除法转成乘法写作 (7 * (1/2)) % 5,再将分数写成幂的形式写作 (7 * 2-1) % 5
    3、由于取模运算结果一定是整数,所以 (7 * 2-1) % 5 结果一定是整数,即说明必定能把 2-1 这个分数转换成某个整数。所以,问题的关键就在于能转换成哪个整数
    4、这时便需要引入乘法逆元的概念了,它可以辅助我们完成模意义的除法模意义的乘法转换

阅读更多
C++数学乘法逆元

学习求 gcd 和 lcm 的方法,学习拓展欧几里得算法、唯一分解定理

gcd 最大公约数


  • 欧几里得算法

    1、求两个数的最大公约数,除了分解质因数法,我们通常使用欧几里得算法(即辗转相除法),其思路如下
    2、求m,n 的最大公约数,就计算 m / n,然后m = nn = m % n,继续循环计算。直到n = 0时停止,这时的m就是最大公约数;或者提前一步,到m % n == 0(结果余数为 0)时停止,这时的n就是最大公约数(推荐后者,在写拓展欧几里得算法时更方便)
    3、gcd 的性质gcd(a, b) = gcd(a, k*a+b)gcd(k*a, k*b) = k * gcd(a, b)a / gcd(a, b)b / gcd(a, b)互素多个整数最大公约数gcd(a, b, c) = gcd(gcd(a, b), c);a 大于 b 时,gcd(a, b) = gcd(a, b-a)

阅读更多
C++exgcdgcdlcm数学

使用快速幂(二进制取幂)快速计算大指数幂的结果,了解幂取模、矩阵快速幂

快速幂


  • 引入

    1、假设我们要计算 an 的值,最朴素的做法是循环 n 次,每次在结果上乘以 a。显然这种做法的时间复杂度为 O(n),但当n 非常大时这种做法的效率仍然较低,而快速幂可以解决这个问题
    2、我们先从一个特例引入:当n 是 2 的幂时,例如求 a64 的值,我们可以按照下表的方式计算。每次将上一次循环得到的结果自乘,就得到了指数下一级 2 的幂的结果,以此类推,便很快就能得到指数所求 2 的幂的结果
    3、而对于任意的 n,例如求 a105 的值,我们可以将指数 n 拆分成多个 2 的幂之和,例如 a105 = a1 + 8 + 32 + 64 = a1 * a8 * a32 * a64,而单独计算这些幂便十分简单了,因此最终只需要将需要的 2 的幂的结果相乘即可
    4、因此,快速幂又称二进制取幂(平方法),其英文为Binary Exponentiation,其时间复杂度仅需 O(log n) 对数级

阅读更多
C++数学快速幂

使用离散化的方式优化更关注相对大小的数列

离散化


  • 离散化

    1、对于元素个数不多值域很大有序无重复数列,且更关注数列的相对大小(而不是绝对大小),可以使用离散化的方式优化程序。离散化本质上是一种哈希,即把一个数字映射为另一个数字
    2、例如对于一个长 100 的有序无重复数列{1, 5, 20, ..., 10^18}(元素最大值为 1018),只判断相对大小关系,可将其映射为{0, 1, 2, ..., 99},便可以代表所需要的相对大小信息
    3、离散化通常可以将大数组零散数据映射到小数组中。例如存储一条 109数轴上的点的值,但却只有较少数据量的一些零散数据,如{[0]:3, [4]:7, [11]:4, [10000]:21},如果开辟 109 的数组不仅会爆栈浪费大量空间。如果使用时只关注下标的相对大小,最好的办法是将有数据的点按照下标离散化{[0]:3, [1]:7, [2]:4, [3]:21},这样便存储到了小数组

阅读更多
C++顺序表离散化

学习双指针的思路,了解同向双指针和相向双指针的常用情景

同向双指针-滑动窗口


  • 例题引入

    1、给定一个已知序列数组元素都是正数(例如{2, 3, 1, 2, 4, 3}),再给定一个target(例如 7),从中找出最短的一个子序列,使子序列的和大于等于target,输出最短子序列的长度
    2、普通的暴力做法是两层循环分别枚举子序列的左右端点,显然这样的时间复杂度为 O(n2),运行速度很慢
    3、另一种思路是使用双指针:由于数组元素都是正数,因此当子序列向右延伸和一定递增。我们先以[0, 3]第一个子序列和为 8;向右移动左指针,发现[1, 3]和为 6不满足条件,便向右移动右指针指向[1, 4]和为 10;继续向右移动左指针,发现[2, 4]和为 7满足条件;以此类推直至末尾。最终发现最短子序列[4, 5]长度为 2
    4、这种思路下,左右指针不需要向左回退,因此两个指针都最多只需要遍历一次数列时间复杂度为 O(n)

阅读更多
C++顺序表双指针

运用二分查找来提高搜索效率,运用二分答案将最值问题转换成判定问题

二分查找


  • 引入

    1、假设对于一个有序数列,例如{1, 2, 3, 5, 5, 5, 8, 9}(实际可能会很长),我们要在里面查找某个元素的位置或其是否存在
    2、如果普通地使用循环遍历,那么时间复杂度为 O(n) 常数级;但如果使用二分查找时间复杂度仅为 O(log n) 对数级,效率大大提升
    3、二分查找每次操作得到当前未比较序列中间下标mid,如果mid对应的值满足(或不满足)条件,则对于有序数列而言,mid前面的一系列值都满足(或都不满足)条件,这样便一次查找了未比较序列一半的元素,便可根据情况调整未比较序列的边界。重复以上操作,直到未比较序列都已经比较,整个序列便按照给定的条件分为了(满足条件/不满足条件)两个组别根据实际情况返回下标即可

阅读更多
C++二分查找二分答案顺序表

学习前缀和与差分,通过前缀和思想快速求区间和,通过差分思想快速实现区间元素的算术运算

一维前缀和


  • 例题引入

    1、设计一个程序,假如有一个已知长度和数据数列(如{1, 3, 7, 5, 2}),程序将m 次询问该数列的任意区间的区间和sum[p, q](例如三次分别询问sum[2, 4]sum[0, 3]sum[3, 4])
    2、简单分析,我们可知如果每次都用循环直接累加,那么单次的时间复杂度为 O(n) ;又因为需要m 次询问,则程序的时间复杂度至少为 O(n*m)。显然当数据量较大时,程序的运行速度很慢。而前缀和时间复杂度只需要 O(n)
    3、对于这类问题,我们可以通过前缀和简化程序,具体如下

阅读更多
C++顺序表前缀和差分

使用 C 语言实现排序算法,了解十大排序思想

注:所有算法的排序原理动图请前往VisualGo观看或前往视频 1|视频 2学习原理



算法复杂度与稳定性


  • 稳定性复杂度口诀

    1、插帽龟(插入、冒泡、归并),它很(稳定性),此外还有基你太稳(基数排序)
    2、插帽龟喜欢选帽插(选择、冒泡、插入),插完就了(平均时间复杂度 O(n2))
    3、快归队(快速、归并、堆),n 老二(平均时间复杂度 O(n*log2n))

阅读更多
C语言排序