算法ACM-ICPC中的数学课件.ppt

1、ACM/ICPC中的数学 数论 组合数学（计数问题）博弈 概率 二、三分，积分预备代数知识 代数结构 半群 群、子群、Lagrange定理 环、交换幺环快速幂乘 半群上元素幂的lgN算法 计算ab%c细节：在32位机器上如何计算64位整数相乘对64位整数取模？矩阵快速幂乘Fibnacci数列题目：字符串接力计数初等数论在ICPC中的几点 Euclid辗转相除法 中国剩余定理 Euler定理一些记号和结论 整除：若a=b*q,b!=0,称b整除a,记作b|a 同余：若c|(b-a),称a,b对c同余，记作a=b(mod c)除法定理：给定a,b两个整数，b 0,则存在两个唯一的整数q,r,使得a

2、=b*q+r,0=r0,均可唯一表示为素数之积:1212kaaaknp pp 最大公约数 最小公倍数 模m的剩余类环 缩系12gcd(,)na aa0,1,1mZm*12(),mmZa aa12lcm(,)na aa N个数的最大公约数给定N个数，求它们的最大公约数Euclid辗转相除法 给定a,b不全为0，求gcd(a,b)结论:复杂度O(lg(b)，可参看算法导论,0gcd(,)gcd(,%),0aba bb abb若若 青蛙的约会（浙江OI）：长的纬度线上，两只青蛙同时往西跳，规定从东往西为正方向建立坐标轴，两只青蛙的坐标分别为x和y，每一跳分别跳m米和n米，二只青蛙每一跳花的时间相同。

3、问两只青蛙能否相遇？拓展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)*bexEuc最直接的实现(C+)struct Tint d,x,y;T exEuc(int a,int b)if(b=0)return T(a,0,0);T tmp=exEuc(b,a%b);return T(tmp.d,tmp.y,tmp.x-(a/b)*tmp.y);/自己证明求得的x,y是否小于max(a,b)中国剩余定

4、理 两两互素，求一次同余方程组 的解 只看n=2，构造 POJ2891(mod),1,2,iixbmin12,nm mm质数表 质数表：保存素因子，标准分解 平方往外筛法(O(n*lglg(n),复杂度未验证)线性筛法(O(n)Euler函数 小于n且与n互素的数的个数 n为素数或素数幂时的 若 设n的标准分解为 ()n121212(,)1()()()n nn nnn，则()n1212kaaaknp ppEuler定理 若(a,n)=1,则 Fermat小定理()1(mod)nan11(mod)pap 多少个连续的8能整除给定的数m(网络赛)质数原根个数(贾怡PKU)大素数检验的Miller-Rabin概率算法 单调函数（数列）二分求解如有序数列的查找方程的数值计算（二分法求数值解）次数(复杂度)：离散的：lg(n);方程的 单峰函数:三分法求峰值：dp优化等 数值积分基本概念Gauss型 外推法，Romberg数值积分