算法.ACM ICPC中的数学.ppt_第1页
算法.ACM ICPC中的数学.ppt_第2页
算法.ACM ICPC中的数学.ppt_第3页
算法.ACM ICPC中的数学.ppt_第4页
算法.ACM ICPC中的数学.ppt_第5页
已阅读5页，还剩13页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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 = b*q+r,00,均 可唯一表示为素数之积: 最大公约数 最小公倍数 模m的剩余类环 缩系 N个数的最大公约数 给定N个数，求它们的最大公约数 Euclid辗转相除法 给定a,b不全为0，求gcd(a,b) 结论: 复杂度O(lg(b)，可参看算法导论 青蛙的约会（浙江OI）： 长的纬度线上，两只青蛙同时往西跳， 规定从东往西为正方向建立坐标轴，两只 青蛙的坐标分别为x和y，每一跳分别跳m米 和n米，二只青蛙每一跳花的时间相同。问 两只青蛙能否相遇？ 拓展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 exEuc最直接的实现(C+) struct T int 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) 中国剩余定理 两两互素，求一次同余方程组 的解 只看n=2，构造 POJ2891 质数表 质数表：保存素因子，标准分解 平方往外筛法(O(n*lglg(n),复杂度未验证) 线性筛法(O(n) Euler函数 小于n且与n互素的数的个数 n为素数或素数幂时的 若 设n的标准分解为 Euler定理 若(a,n)=1,则 Fermat小定理 多少个连续的8能整除给定的数m(网络赛) 质数原根个数(贾怡PKU) 大素数检验的Miller-Rabin概率算法 单调函数（数列）二分求解 如有序数列的查找 方程的数值计算（二分法求数值解） 次数(复杂度) ：离散的
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论