1、ACM中的数学问题数论武汉科技大学引言w 在 ACM竞赛中 ,经常可以看到数学问题的身影w 可以是纯数学问题 ,也可以是需要利用数学上的一些公式 ,定理 ,算法来辅助解决的问题w 会者不难 ,而不会的选手在赛场上一般很难推出公式或进行证明w 往往想起来费劲 ,写起来却很轻松常见的数学问题w 数论w 组合数学w 计算几何w 博弈论w 线性代数w 高等数学w 线性规划w 概率统计w .本讲内容w 基本上是最基础的 ,同时也是 ACM竞赛中最常见的数学问题w 对一些数学公式 ,定理进行简略地推导或证明 ,从而加深对它们的理解和认识 ,也方便记忆w 往届 ACM竞赛中的数学问题数论w 简而言之 ,数论
2、就是研究整数的理论w 在 ACM竞赛中 ,经常用到与数论相关的知识w 纯数论的题目不多 ,大部分是和其他类型的问题结合起来的数论的历史w 自古以来 ,许许多多的数学家研究过与数论有关的问题w 直到十九世纪 ,数论才真正形成了一门独立的学科w 数论是一门高度抽象的学科 ,长期处于纯理论研究的状态 ,曾经被认为是很难有应用价值的w 随着计算机科学的发展 ,数论得到了广泛的应用主要内容w 第一部分 :同余相关整除的性质欧几里德算法扩展欧几里德算法中国剩余定理w 第二部分 :素数相关算术基本定理欧拉定理素数测试Pollard rho方法第一部分 同余相关 w 整除的基本性质w 欧几里德算法w 扩展欧几
3、里德算法w 中国剩余定理整除的符号w a|ba是 b的约数（因子）， b是 a的倍数对于两个不为 0的整数整除，被除数的绝对值大于等于除数的绝对值 . 对于正整数来讲， a|b 意味着 b大， a小整除的基本性质w 性质 1： a|b,b|c = a|cw 性质 2： a|b = a|bcw 性质 3： a|b,a|c = a|kblcw 性质 4： a|b,b|a = a=bw 性质 5： a=kbc = a,b的公因数与 b,c的公因数完全相同w 证明：假设 d是 b,c的公因数，即 d|b, d|c。利用整除性质 3， d整除 b,c的线性组合，故 d|a。所以 d是 a,b的公因数反之，如果 d是 a,b的公因数，也能证出 d是 b,c的公因数
