信息奥赛中的数学方法.pptx

信息学竞赛中的数学方法清华大学计算机系 胡泽聪目录 基础数论模意义下的运算费马小定理、欧拉定理与乘法逆元快速幂与快速乘法辗转相除法与高精度GCD线性同余方程与拓展欧几里得算法筛法与质因数分解 组合数学入门排列与组合常用公式简单的组合数取模常用数列容斥原理与禁位排列 位运算及bitset基础数论Basic Number Theory基本概念带余除法模数、取模同余因子互质最大公因数模意义下的运算很多题目的基础加减乘法在模意义下封闭除法则不同费马小定理?要求为质数，且不是的倍数。特别地，可以为。证明思路：。欧拉定理?要求与互质。为欧拉函数，定义为小于等于且与互质的数的个数。设，则。对于质数而言，。乘法逆元?除法是乘法的逆运算。有。由欧拉定理，。则为在模意义下的乘法逆元，等价于，记作。当然，前提是和互质。一些大质数?（不常用）奇怪的生日快速幂?由于模数通常很大，求逆元需要算的幂次也就很大。朴素的做法无法接受。快速幂?考虑，将按二进制位分解。如果我们知道可以把的所有为的二进制位对应的次幂相乘得到。复杂度。快速幂：代码快速乘法?有时模数实在太大，以至于两数相乘无法用longlong表示。写高精度乘法显然不划算。类似快速幂，处理出。每次只要乘，一般来说可以接受。要是还存不下就没办法了。最大公因数（GCD）?Greatest Common Divisor，记作。一些性质：更相减损术?利用。用大数减小数，得到新的一对和，并重复以上过程。复杂度无法得到保证。辗转相除法?假设，那么更相减损术会一直使，直到。这其实就是。于是就得到了辗转相除法。复杂度为。辗转相除法：代码高精度加减乘法?用字符串表示数字，模拟竖式计算。加减法复杂度，乘法复杂度，为数字位数。常用优化：压位。高精度除法?类似竖式除法。在除数末尾补尽量多的，使得其恰好小于被除数；进行数次高精度减法，直到被除数小于除数；令商加上减法次数；如果除数末尾还有之前补上的，则除数除以，商乘以，跳转到第2步；剩下的被除数即为余数。复杂度。高精度GCD?辗转相除？可能进行次除法运算，高精度除法太慢。考虑更相减损，加入一些优化：如果和都是偶数，直接令两数除以，并令GCD乘以；如果和一奇一偶，则除去偶数的所有的因子；如果和都是奇数，则令大数减小数，此时必然得到一个偶数。复杂度如何？每两步就能令一个数除以2，故减法次数为。总复杂度。线性同余方程?形如，求的值。一些性质：如果，则方程有且仅有一个解；方程有解，且解数为。而同余方程与不定方程同解。拓展欧几里得算法?拓展欧几里得算法在求出的同时，还能顺带解出不定方程的一组解。这个不定方程等价于线性同余方程，所以必然有解。拓展欧几里得算法??求出GCD之后，将整个过程倒过来：考虑的辗转相除过程：得到拓展欧几里得算法?求出GCD之后，将整个过程倒过来：?依次带入得：解得。拓展欧几里得算法：代码求解线性同余方程?之前说到同余方程与不定方程同解。移项得，而令使用拓展欧几里得算法求解的解；则原方程的解为、。分解质因数?一个数最多有一个大于的质因子。枚举所有不超过的质数并试除；如果剩下的，那么这也是一个质因子。复杂度为。枚举因子?一个数的每个大于等于的因子必然对应一个小于等于的因子。算法和分解质因数基本一样。因子个数的上界，但实际上达不到这个上界。筛法?预处理的所有质数。是质数；对于每个质数，枚举其不超过的所有倍数，标记为合数。就这么简单。复杂度为。（调和级数）筛法?我们还可以顺便处理出内每个数的最小值因子。有了这个信息之后，便可以在的时间内分解质因数。基础数论：例题Basic Number Theory: ExamplesNOIP2012 D2T1同余方程题解题面拓展欧几里得的直接应用。也可以直接算逆元。求的最小正整数解。。?POJ1061青蛙的约会题解题面假设赤道是长度为的数轴，坐标为的整数，跳过之后会从一侧跳出来。两只青蛙分别在和的位置，每次分别可以跳和格。问最少跳几次之后，两只青蛙会相遇。。其实就是求关于的同余方程的最小非负整数解。化一下即。判断是否有解之后解之即可。??HDU2824The Euler Function题解题意求。。（此处为原题削弱版）用筛法处理出每个数的最小质因子，并利用它来在时间内计算的值。??POJ2480Longge`s Problem题解题意求。。转换思路：的值肯定是的因子。设其为。那有多少满足？同时除以，即问有多少满足？而这个个数就是。所以答案就是。注意在求时应利用的质因子分解结果。总复杂度约为。??SGU106The Equation题解题意求在且的条件下有多少组解。所有数字绝对值均不超过。先考虑几种特殊情况：；（无解）；和中有且仅有一个；（无解）。对于剩下的情况，先将变为非负数，并求出一组可行解。之后便是求有多少满足且，直接做除法取整即