a’y + b’x – b’*(x div y)*y = d b’x + (a’– b’*(x div y))*y = d 有a = b’ b = a’ - b’*(x div y) 边界：y = 0时，a = 1, b = 0
解模方程ax mod b = c 等价于解出ax + by = c
无解的条件c mod gcd(a,b) <> 0
求解ax +by = c
令d = gcd(a, b), c’ = c div d
求解原方程等价于求解ax + by = d, 求完后将答案乘上c’即可
求ax mod b = c的最小正解的方法
先求出一组ax + by = c的可行解x,y（实际上我们只要x） 由a(x + k*b) mod b = c
所以我们可以通过给x加上若干倍b使得a恰好大于0
实际操作时，只要取x’ = x mod b就可以了，如果x’< 0 则 x’ := x’ + b
解同余方程组的方法：每次合并两个模方程，合到最后就能够解出来了 核心操作：合并 x mod a1 = b1 x mod a2 = b2
令x = a1*y + b1
则(a1*y + b1) mod a2 = b2 a1*y mod a2 = b2 - b1
可以用扩展欧几里得求出y,从而求出最小正x同时满足两个方程 合并之后变成x’ mod lcm(a1, a2) = x mod lcm(a1, a2) 以此合并求解即可
将带系数的方程化为不带系数的方法： ax mod b = c ? ax + by = c ?
利用扩展欧几里得可解得x, y
那么x的通解可以表示为x + k*(b div gcd(a, b)) 因此，原方程等价于x’ mod (b div gcd(a, b)) = x, x’是新的未知数,x是上面用扩展欧几里得解出来的东西，成功地等价地把系数消掉了
素数和整除性问题 判断素数的方法：
O(sqrt(n)):从2枚举到sqrt(n)逐一判断即可 均摊O(ln(n))的方法：筛选法
利用费马小定理可以O(k*logn)地检验质数，但有一定概率出错（k是检验次数）
组合计数类问题 基本：
排列和组合：C(N,M) = N!/(M!(N-M)!) P(N,M) = N!M!
容斥原理：在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，
人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
容斥原理的一点思考：我们可能会碰到这样一类问题，题目要我们统计一个集合，但这个集合本身是非常难以计算，甚至根本就无法计算时，我们可以考虑把这个集合“设”出来，因为不可计算不代表不可解，有时候我们是可以用容斥原理列出关于这个集合的方程，然后再利用别的信息解出这个集合，从而避免了麻烦的直接计算。 Pólya定理和Burnside引理 内容：
Burnside引理：本质不同的染色方案个数为
∑作用在一个染色方案上的每个置换的不动元素个数/|G| 经典应用：poj 2888有限制的环染色方案统计，循环同构
经典优化：朴素的想法如果是枚举每次跳多少步，然后循环节长度l = gcd(i, n)，那就可以改为枚举l，然后用欧拉函数求出满足gcd(i, n) = l的i的个数 方法： L = gcd(i, n) Gcd(i/l, n/l) = 1
又i/l <= n/l，所以满足条件的i的个数= phi(n/l)
Pólya定理：本质不同的染色方案个数为（m是颜色个数） ∑m^(每种置换中的循环节个数)/|G| 经典应用：HNOI 2009 图同构计数
经典优化：不直接统计原来要统计的东西，转而考虑每个需要被统计的东西会被统计多少次，然后集中处理，通常“本质不同”的被统计的东西相对于原来for的东西是非常少的，所有复杂度会大幅降低，通常的“集中处理”方法是快速幂。
七、 计算几何
计算几何题的最大特点就是编程复杂度极高，大部分题目都是思想简单，实现复杂，考察选手的编程实现能力，而且精度问题也往往需要仔细考虑 基础知识： 旋转、平移
Rotate(var Px,var Py, A) // 将向量(Px, Py)以原点为中心逆时针旋转A（弧度） Qx = Px, Qy = Py Px = Qx * cos(A) – Qy * sin(A) Py = Qx * sin(A) + Qy * cos(A) Move(var Px, var Py, Qx, Qy) // 将向量(Px, Py)按照(Qx, Qy)平移 Px = Px + Qx Py = Py + Qy 过两点PA(xA, yA), PB(xB, yB)的直线L: Ax + By + C = 0： BuildLine(PA, PB, L) A = yA – yB B = xB – xA C = xA * yB – yA * xB 求直线L: Ax + By + C = 0上两个不同的点PA(xA, yA), PB(xB, yB) BuildPoints(L, PA, PB) T = A2 + B2 xA = - C * A / T, xB = xA + B yA = - C * B / T, yB = yA - A （由以上两条，可在直线的两种表示方式之间进行转化） 求点P(xP, yP)到直线L(PA-PB)的距离
Distance (P, L) Distance = |(PA – P)×(PB – P)| / |PA – PB| 过点P(xP, yP)平行与直线L: (PA – PB)的直线： GetLine(P, L) Return Line(P, P + PA – PB) 求点P(xP, yP)关于直线L(PA-PB)的对称点Q GetSymmetryPoint(P, L, Q) PB = PB – PA, P = P – PA A = getAngle(P to PB) Rotate(P, 2 * A) Q = P + PA 求两直线L1: A1 x + B1 y + C1 = 0与L2: A2 x + B2 y + C2 = 0的交点P(xP, yP)
GetIntersection(L1, L2, var P) S = A1 * B2 – A2 * B1 X = C1 * B2 – C2 * B1 Y = A1 * C2 – A2 * C1 若S = 0 若X = Y = 0，则L1、L2重合； 否则无交点 否则xP = -X / S, yP = -Y / S 求两直线L1: (PA – PB), L2: (PC – PD)的交点P(xP, yP) 求两线段S1: (PA – PB), S2: (PC – PD)的交点P(xP, yP)
GetIntersection(S1,S2, var P) 检查直线L1: (PA – PB), L2: (PC – PD)的交点P(xP, yP) 若L1, L2重合，则直接在直线上判断S1、S2的相交情况 否则 若P同时在S1、S2上则P为S1、S2的交点 否则没有交点 重要知识点： 凸包
计算几何中最基本也是最重要同时也是非常有用的一个知识点，根据经验，很多几何题都可以不管别的，先求个凸包再说，性质说不定就出来了。
凸包的常用求法是graham扫描法，先把点按横坐标排序，再一边扫描，一边用个栈维护凸包上的点，叉积判断当前栈顶的点是否应该被剔除复杂度是排序的复杂度O(nlogn)
旋转卡壳
其实这是一种思想，一类方法，以维护对踵点为例（对踵点即每个点在凸包上最远点），核心是利用上一次的信息，当i点在凸包上逆时针转动的时候，对踵点j也会在凸包上逆时针转动，而且是单调移动的，也就是说，i+1的对踵点不会比i的对踵点靠前。这样，就可以用个指针维护对踵点，对应维护就可以了，总的复杂度还是O(n)。应用这个思想，可以均摊O(1)地对应维护一些因变量，只要该变量关于自变量的变化过程单调非降。经典例题HNOI2007day1最小矩形覆盖（维护凸包上的向前、向左、向右的最远点）
半平面交（O(nlogn)算法）详细介绍见题解篇
凸多边形的重心、面积，空间多面体的体积：核心是利用叉积
八、 字符串
Kmp：核心是构造next函数，该函数可感性地理解为“失败指针”，即如果在该位匹配失败则指针应该跳到哪里去，然后可以以线性时间复杂度完成单串模式匹配问题
Ac自动机：见数据结构总结，可以做到O(n)的多串模式匹配
后缀数组：本质是给所有后缀排序，核心是height数组，具体介绍见题解篇 一般实现用O(nlogn)的倍增算法
九、 各种怪怪的算法
1. 高斯消元（解xor方程组）
本质是加减消元，每次用一个方程去消掉其他方程中的一个未知元，构造出“阶梯矩阵”，然后反代逐个求解
Xor方程组类似，参考poj 1830 开灯问题题解 2. 拉格朗日逐差法
给你一个多项式函数的前n项，要你求第n+1项 20100902未完成的序列
3. 模拟退火（爬山搜索、随机化调整）
随机调整使解不断变优，有时候需要按一定几率给不优的解一点生存空间，防止当前解没有办法通过调整更优了而陷入死胡同
经典例题：20060423圆桌会议、graceful树的优美标号、CTSC2007激光坦克
4. sg函数与组合游戏
核心就是nim取石子游戏，基本上所有组合游戏都可以转化为nim游戏，通过构造sg函数、分解游戏来解决一类平等博弈问题
核心知识点：SG（i） = { x | not ( x in { SG ( i的后继状态) } ) , x in N )，用中文来讲就是i状态的sg值等于i后继状态的sg函数值中没有出现过的最小自然数（可以为0） 定理：sg( i1 , i2 , i3 , i4 , i5 … , im ) = sg( i1 ) xor sg ( i2) xor sg( i3 ) xor … xor sg( im ) 那么我们就可以预处理出所有 sg( i )，然后快速地判断必胜必败态了 更加详细的介绍：
王晓珂《解析一类组合游戏》
组合游戏略述——浅谈SG游戏的若干拓展及变形 从“k倍动态减法游戏”出发探究一类组合游戏问题 浅谈如何解决不平等博弈问题
5. 线性规划
——半平面交：只能解决两个参量的线性规划问题，具体做法见《计算几何》 ——单纯形法：实现很简单，复杂度在一般情况下非常好，但最坏是O(n!)的，有一定实际价值（其实单纯形还能解决一大堆能划归为线性规划问题的问题，比方说网络流就可以看成是要求满足流量平衡方程和容量限制的一个线性规划问题，），详细介绍及数学证明参考《算法导论》