NOIP数论.pptx

数学 素数和整除问题 素数筛法O NlogN 算法不再赘述介绍一种O N 算法 将i从2到N扫描从前i未被筛过则存入prime数组用j从1循环 用i prime j 筛素数 若imodprime j 0跳出 不难发现 每个合数被删仅一次x a k1 b k2 a b为素数 a b i a k1 1 b k2prime j a时x被筛去复杂度为O N for i 2 i n i if hash i prime tot i for j 1 prime j i n j hash prime j i 1 if i prime j 0 break 素数和整除问题 最大公约数与最小公倍数高精度GCD 模拟单精度实现过程太过麻烦设a b 则Gcd a b Gcd a 2 b 2 2 a 2 0b 2 0 Gcd a b 2 a 2 1b 2 0 Gcd a 2 b a 2 0b 2 1 Gcd b a b a 2 1b 2 1为什么是log级别的 素数和整除问题 NOIp2009 已知Gcd x a0 a1Lcm x b0 b1求满足条件的x个数 a0 a1 b0 b1 ka1否则kx ka1若kb0 kb1则kx kb1否则kx kb1可由此确定每个素数因子的范围乘法原理求总解数sqrt 2 000 000 000 内仅有4000 素数 AC 扩展欧几里得 扩展欧几里得 如何求解ax by gcd a b 回顾欧几里得算法intgcd inta intb returnb gcd b a b a 递归到底时a gcd a b b 0 令x 1 y 0 满足ax by gcd a b a b a a b bax by c bx a a b b y cxa yb c y a x a b y b c回溯时令x y y x a b y 扩展欧几里得 代码求ax by gcd a b includeintextended gcd inta intb int x int y intret tmp if b x 1 y 0 returna ret extended gcd b a b x y tmp x x y y tmp a b y returnret intmain inta b x y z scanf d d 扩展欧几里得 求解ax by c 判断c是否被gcd a b 整除 整除则有解 反之无解求解ax by gcd a b 若ax by gcd a b 的解为 x y 则ax by c的解 x y c gcd a b x c gcd a b y 如何求出不定方程的所有整数解 x k b gcd a b y k a gcd a b 为所有合法解其中k Z 简单排列组合计数 排列与组合排列数 N个不同物体不重复地取M个做排列的方法数P N M N N M 组合数 N个不同物体不重复地选取M个的方法数C N M N N M M 可重排列 K种元素 重数分别为n1 n2 nk 所有n ni个元素的全排列数为n n1 n2 nk K种元素 重数均为无限大 选取r的的组合数为C r K 1 r 可以转化为矩阵内从左上角到右下角只能向右走或下走的方法数问题 排列组合 组合公式的推论c n m c n n m c n m c n 1 m 1 c n 1 m 卡特兰数h n C 2n n n 1 n 0 1 2 错排公式递推式 M n n 1 M n 2 M n 1 特殊地 M 0 M 1错排公式为M n n 1 2 1 3 1 n n 容斥原理研究有限集合的交或并的计数 DeMorgan定理 论域U 补集 有 容斥原理 a b DeMogan定理的推广 设 容斥原理 容斥原理 最简单的计数问题是求有限集合A和B的并的元素数目 显然有 即具有性质A或B的元素的个数等于具有性质A和性质B的元素个数 4 容斥原理 5 容斥原理指的就是 4 和 5 式 容斥原理 例4 求不超过120的素数个数 例 因 故不超过120的合数必然是2 3 5 7的倍数 而且不超过120的合数的因子不可能都超过11 设为不超过120的数的倍数集 2 3 5 7 例 例 例 例 注意 27并非就是不超过120的素数个数 因为这里排除了2 3 5 7着四个数 又包含了1这个非素数 2 3 5 7本身是素数 故所求的不超过120的素数个数为 27 4 1 30 例 向量 需要注意的细节 常用头文件 include计算几何中一般来说使用double型比较频繁 请注意数据类型的选择 该用实数的时候就用double 而float容易失去精度 判断double型的x是否为0 应当用x eps 或者fabs x eps 其中eps代表某个精度 常常取eps 0 000001 还有其他类似情况也要注意double类型的精度问题 int x eps 避免x 4 999999999 需要注意的细节 圆周率取3 141592654或者更精确 或者用acos 1 角度制和弧度制的转换 C C 中的三角函数均为弧度制尽量少用除法 开方 三角函数 容易失去精度 用除法时注意除数不为0输出的时候要小心 0 00000 比如a 0 0000001 printf 5lf a 向量及其运算 计算几何中经常使用向量 而且基本上都是二维的 下面用 代表三个向量 x 0 y 0 x 1 y 1 x 2 y 2 某些题目需要经常使用向量运算 因此对于这类问题最好建立构造类型或者类来表示向量 并将向量之间的运算进行重载一般需要重载加法 减法 和向量乘法 向量及其运算 structpoint 构造点的数据类型 也可作向量使用doublex doubley v1 v2 pointoperator pointp1 pointp2 doubleoperator pointp1 pointp2 向量及其运算 加法 x 0 x 1 y 0 y 1 满足平行四边形法则图形表示减法图形表示 向量及其运算 向量有两种乘法 内积 数量积 点积 和外积 向量积 叉积 一般是要根据题目需要选择其中一个重载 多数情况是重载外积 其中内积 x 0 x 1 y 0 y 1 外积 x 0 y 1 x 1 y 0 向量及其运算 内积的几何意义 在 的投影 与 的长度乘积外积的几何意义 和 所张成的平行四边形的有向面积外积在计算几何的题目当中经常使用 外积的应用 判断外积的符号 右手定则如图 0如果 0则等价于两个向量共线 同向或反向 可以用此判断三点共线问题 当然 这里的 0在实际编程的时候要用一个精度来控制 外积的应用 利用外积求三角形面积已知三个顶点坐标为 a 0 b 0 a 1 b 1 a 2 b 2 则三角形面积为注意别忘记取绝对值 这里利用面积是否为0也可以考察三点共线问题这个方法求面积比海伦公式或者其他方法要好 外积的应用 由求三角形面积的方法可以推广求凸多边形面积如图 从一固定点出发 向其他各点引辅助线 这样就分割成了若干个三角形 利用上式求出每个三角形的面积再相加即可 整点多边形 整点多边形是指顶点的横纵坐标均为整数由外积导出的面积计算公式可以看出 整点多边形的面积或为整数 或为整数 2 Pick公式 整点多边形的面积 内部整点个数 边上的整点个数 2 1 NKOJ1159 Triangle计算几何中的公式有不少 需要积累 三角形的一些性质 如何判断点是否在三角形内部 此点与三角形三个顶点相连 出现三个三角形 如果这三个三角形的面积之和等于原三角形面积 那么该点在内部推广 可用来判断点是否在凸多边形内部 判断点在直线上 利用三点共线的等价条件 0直线上取两不同点P1 P2 若点P在直线上 则fabs P1 P P2 P eps如果该题目需要编写求三角形面积的函数 那直接判断这三个点形成的三角形面积是否 eps 判断点在线段上 判断点P x y 是否在线段P1P2上 其中P1 x1 y1 P2 x2 y2 需要验证两条 1 点P在P1P2所在直线上 即三点共线 2 点P在P1P2为对角线的矩形内其中 2 利用min x1 x2 x max x1 x2 min y1 y2 y max y1 y2 用高斯消元法解线性方程组 线性方程组的一般形式 先看一个例子 22 1314 122 5 1 56 5 2 1314 12 0 8755 25 2 0 5 0 625 得出 x3 5 25 0 875 6x2 2 1 x3 4 1x1 1 1 x2 3x3 2 9 消元过程 a1 1 1 a1 2 1 a1 n 1 b1 1 a2 1 1 a2 2 1 a2 n 1 b2 1 an 1 1 an 2 1 an n 1 bn 1 注 用上标 k 表示第k次消元前的状态 第1次消元 第1行的乘数 i 2 3 n a1 1 1 a1 2 1 a1 n 1 b1 1 a2 2 2 a2 n 2 b2 2 an 2 2 an n 2 bn 2 得到新的增广矩阵 i j 2 3 n 第k次消元 第k行的乘数 i k 1 k 2 n 消元过程 a1 1 1 a1 2 1 a1 n 1 b1 1 a2 2 2 a2 n 2 b2 2 ak k k ak n k bk k an k k an n k bn k 第k次消元前的增广矩阵 增广矩阵的变化 i j k 1 k 2 n 回代过程 a1 1 1 a1 2 1 a1 n 1 b1 1 a2 2 2 a2 n 2 b2 2 an n n bn n 最后得到的增广矩阵 最终结果的计算 为什么要选主元素 前面介绍的消元法都是按照自然顺序 即x1 x2 xn的顺序消元的 有 所以每一次消元的主元素都不能为0 如果按照自然顺序消元的过程中出现的ak k k 0 那么消元无法继续进行下去 或者 ak k k 很小 也会严重影响计算精度 为什么要选主元素 例如 假设运算过程中使用单精度实数 10 1011112 10 1011 1010 1010 解得 x1 0 x2 1这个解与第二个方程差异很大 究其原因 因为消元过程中第一个方程所乘的系数过大 使得上式 吃掉 了下式 所以在结果中根本无法体现下式 但如果调整一下顺序 11210 1011 11211 解得 x1 1 x2 1 这个解基本符合原方程所以每次消元的主元素的绝对值应该尽可能大 使得与主行相乘的乘数尽可能小 选主元素 a1 1 1 a1 2 1 a1 n 1 b1 1 a2 2 2 a2 n 2 b2 2 ak k k ak n k bk k al k k al n k bl k an k k an n k bn k 进行第k次消元时 将ak k与以下各元素 包括ak k 进行比较 将其中的最大者所在行与第k行交换 无解的情况 如果在消元的过程中 增广矩阵出现这样一行 左侧各未知数的系数都为0 而右侧的常数项不为0 则意味着方程组无解 无数组解的情况 在消元过程中 出现这样一行 各未知数的系数和常数项都为0 这相当于少了一个方程 也就是接下来的消元过程中 方程的个数少于未知数的个数 方程要么无解 要么有无数组解 下面讨论对于这样的方程 如何得到一组解 先看这样一个方程 423921142125 423900 0 5 0 5000 50 5 如果继续消元 消第2列 必须保证a2 2 0 可是第2列中不存在非0的项 无数组解的情况 423900 0 5 0 5000 50 5 只能够把第3列的元素作为第2次消元的主元素 进行消元 423900 0 5 0 50000 第2次消元得到的元素全部为0 所以第三行元素已失去意义 x2没有做过主元素 可随意取值 再进行回代 得到一组可行解 如令x2 0 x3 1 x1 1 5 对于一般的线性方程组 先进行消元 每次消元前找到系数不完全为0的列 相应的元素作为此次消元的主元素 直至第k次消元时 得到的新元素全部为0 这时把各未知数分为两种 第k 1列至第n列对应的未知数 可以将这些未知数随意取值 第1列至第k列对应的未知数 这些未知数的值在回代过程中确定 性能分析 时间复杂度 O n3 消元O n3 选主元素 O n2 回代O n2 空间复杂度 O n2 增广矩阵O n2 如使用全选主元素 还需一个存储列与元素对应信息的表 为O n 精度 由于采用实数运算 另外每一次 第一次除外 消元都要使用以前消元产生的结果 每一次回代都要使用消元结果和其它回代结果 所以累积误差比较严重 该方法只能够求得近似解 但是可以根据具体需要进行相应改进 整数线性方程组的精确解法 前面讨论了对于一般线性方程组通过实数运算得到近似解的算法 而在一些问题中 常常要求精确解 这里讨论一下系数 常数项和解均为整数的线性方程组的精确解法 前面是用这种方法消元的 显然这里进行的是实数运算 整数线性方程组的精确解法 由于不能够保证ai k k 是ak k k 的倍数 要想消元 必须使两行分别乘以一个乘数 方程较多时 系数有可能越来越大 到一定程度有可能导致系数越界 因此要随时对各行化简 即把这一行中所有元素除以这些元素的最大公约数 但是 无论如何 这也保证不了不会发生越界 因此这种算法一般适用于系数 未知数范围较小 未知数个数较少的方程 异或方程组 异或方程组就是形如这个样子的方程组 M 0 0 x