算法ACM-ICPC中的数学课件

ACM/ICPC中的数学ACM/ICPC中的数学1数论组合数学（计数问题）博弈概率二、三分，积分数论2预备代数知识代数结构半群群、子群、Lagrange定理环、交换幺环预备代数知识代数结构3快速幂乘半群上元素幂的lgN算法计算a^b%c

细节：在32位机器上如何计算64位整数相乘对64位整数取模？矩阵快速幂乘

Fibnacci数列

题目：字符串接力计数快速幂乘半群上元素幂的lgN算法4初等数论在ICPC中的几点Euclid辗转相除法

中国剩余定理

Euler定理初等数论在ICPC中的几点5一些记号和结论整除：若a=b*q,b!=0,称b整除a,记作b|a同余：若c|(b-a),称a,b对c同余，记作a=b(modc)除法定理：给定a,b两个整数，b>0,则存在两个唯一的整数q,r,使得a=b*q+r,0<=r<b成立唯一分解定理（标准分解）：任一自然数n>0,均可唯一表示为素数之积:

一些记号和结论6最大公约数最小公倍数模m的剩余类环

缩系最大公约数7N个数的最大公约数

给定N个数，求它们的最大公约数N个数的最大公约数

给定N个数，求它们的最大公约数8Euclid辗转相除法给定a,b不全为0，求gcd(a,b)结论:复杂度O(lg(b))，可参看《算法导论》Euclid辗转相除法给定a,b不全为0，求gcd(a,b)9青蛙的约会（浙江OI）：

长Ｌ的纬度线上，两只青蛙同时往西跳，规定从东往西为正方向建立坐标轴，两只青蛙的坐标分别为x和y，每一跳分别跳m米和n米，二只青蛙每一跳花的时间相同。问两只青蛙能否相遇？青蛙的约会（浙江OI）：

长Ｌ的纬度线上，两只青蛙同时往西跳10拓展Euclid算法给定a,b不全为0，求d,x,y使得

d=gcd(a,b)=a*x+b*y

注：不唯一，调整下就可以作为另一组解在Euclid算法上作一点手脚:

设a>b>0,a=b*q+c(除法定理)

若d=x’*b+y’*c

则d=y’*a+(x’–q)*b拓展Euclid算法给定a,b不全为0，求d,x,y使得

d11exEuc最直接的实现(C++)structT{ intd,x,y;};TexEuc(inta,intb){ if(b==0)returnT(a,0,0); Ttmp=exEuc(b,a%b); returnT(tmp.d,tmp.y,tmp.x-(a/b)*tmp.y);}//自己证明求得的x,y是否小于max(a,b)exEuc最直接的实现(C++)structT{12中国剩余定理两两互素，求一次同余方程组

的解

只看n=2，构造

POJ2891中国剩余定理两两互素，求一次同余方程组

13质数表质数表：保存素因子，标准分解平方往外筛法(O(n*lglg(n)),复杂度未验证)线性筛法(O(n))质数表质数表：保存素因子，标准分解14Euler函数小于n且与n互素的数的个数n为素数或素数幂时的若设n的标准分解为Euler函数小于n且与n互素的数15Euler定理若(a,n)=1,则Fermat小定理Euler定理若(a,n)=1,则16多少个连续的8能整除给定的数m(网络赛)

质数原根个数(贾怡@PKU)

大素数检验的Miller-Rabin概率算法多少个连续的8能整除给定的数m(网络赛)

17单调函数（数列）二分求解

如有序数列的查找

方程的数值计算（二分法求数值解）

次数(复杂度)：离散的：lg(n);方程的单峰函数:三分法求峰值：dp优化等数值积分基本概念

Gauss型外推法，Romberg数值积分单调函数（数列）二分求解

如有序数列的查找

方程的数值计算（18ACM/ICPC中的数学ACM/ICPC中的数学19数论组合数学（计数问题）博弈概率二、三分，积分数论20预备代数知识代数结构半群群、子群、Lagrange定理环、交换幺环预备代数知识代数结构21快速幂乘半群上元素幂的lgN算法计算a^b%c

细节：在32位机器上如何计算64位整数相乘对64位整数取模？矩阵快速幂乘

Fibnacci数列

题目：字符串接力计数快速幂乘半群上元素幂的lgN算法22初等数论在ICPC中的几点Euclid辗转相除法

中国剩余定理

Euler定理初等数论在ICPC中的几点23一些记号和结论整除：若a=b*q,b!=0,称b整除a,记作b|a同余：若c|(b-a),称a,b对c同余，记作a=b(modc)除法定理：给定a,b两个整数，b>0,则存在两个唯一的整数q,r,使得a=b*q+r,0<=r<b成立唯一分解定理（标准分解）：任一自然数n>0,均可唯一表示为素数之积:

一些记号和结论24最大公约数最小公倍数模m的剩余类环

缩系最大公约数25N个数的最大公约数

给定N个数，求它们的最大公约数N个数的最大公约数

给定N个数，求它们的最大公约数26Euclid辗转相除法给定a,b不全为0，求gcd(a,b)结论:复杂度O(lg(b))，可参看《算法导论》Euclid辗转相除法给定a,b不全为0，求gcd(a,b)27青蛙的约会（浙江OI）：

长Ｌ的纬度线上，两只青蛙同时往西跳，规定从东往西为正方向建立坐标轴，两只青蛙的坐标分别为x和y，每一跳分别跳m米和n米，二只青蛙每一跳花的时间相同。问两只青蛙能否相遇？青蛙的约会（浙江OI）：

长Ｌ的纬度线上，两只青蛙同时往西跳28拓展Euclid算法给定a,b不全为0，求d,x,y使得

d=gcd(a,b)=a*x+b*y

注：不唯一，调整下就可以作为另一组解在Euclid算法上作一点手脚:

设a>b>0,a=b*q+c(除法定理)

若d=x’*b+y’*c

则d=y’*a+(x’–q)*b拓展Euclid算法给定a,b不全为0，求d,x,y使得

d29exEuc最直接的实现(C++)structT{ intd,x,y;};TexEuc(inta,intb){ if(b==0)returnT(a,0,0); Ttmp=exEuc(b,a%b); returnT(tmp.d,tmp.y,tmp.x-(a/b)*tmp.y);}//自己证明求得的x,y是否小于max(a,b)exEuc最直接的实现(C++)structT{30中国剩余定理两两互素，求一次同余方程组

的解

只看n=2，构造

POJ2891中国剩余定理两两互素，求一次同余方程组

31质数表质数表：保存素因子，标准分解平方往外筛法(O(n*lglg(n)),复杂度未验证)线性筛法(O(n))质数表质数表：保存素因子，标准分解32Euler函数小于n且与n互素的数的个数n为素数或素数幂时的若设n的标准分解为Euler函数小于n且与n互素的数33Euler定理若(a,n)=1,则Fermat小定理Euler定理若(a,n)=1,则34多少个连续的8能整除给定的数m(网络赛)

质数原根个数(贾怡@PKU)

大素数检验的Miller-Rabin概率算