2010北大ACM暑期讲义数学题.pdfVIP

ACM 中的数学问题 北京大学ACM竞赛队队员 林舒 引言 在ACM竞赛中,经常可以看到数学问题的身影 可以是纯数学问题,也可以是需要利用数学上 的一些公式,定理,算法来辅助解决的问题 会者不难,而不会的人在赛场上一般很难推出 公式或进行证明 往往想起来费劲,写起来却很轻松 常见的数学问题 数论 组合数学 博弈论 线性代数 高等数学 线性规划 概率论 ... 本讲内容 简单数论 Polya定理 SG函数 与矩阵有关的问题 本讲内容 基本上是最基础的, 同时也是ACM竞赛中 最常用的数学算法 一些数学定理,公式的简略证明或推导,从 而加深对它们的理解和认识,也方便记忆 往届ACM竞赛中的数学问题 数论 简而言之,数论是研究整数的理论 在ACM竞赛中,经常用到数论的相关知识 纯数论的题目不多,大部分是和其他类型 的问题结合起来的 约数,倍数,模线性方程,欧拉定理,素数 整除的性质 性质1:a|b,b|c = a|c 性质2:a|b = a|bc 性质3:a|b,b|c = a|kb ±lc 性质4:a|b,b|a = a= ±b 性质5:a=kb ±c = a,b 的公因数与b,c的 公因数完全相同(利用性质3) 最大公约数 最小公倍数 欧几里德算法(辗转相除法,短除法) 原理:若a≡r(mod b),则gcd(a,b)=gcd(b,r)(利 用性质5证明) 算法步骤(递归实现): 整数a,b,假设ab 若b=0,则gcd(a,b)=|a|;否则gcd(a,b)=gcd(b,a%b) 最小公倍数:lcm(a,b)=a*b/gcd(a,b) 解二元模线性方程 二元模线性方程(二元一次不定方程):形 如ax≡c(mod b) 或ax+by=c 扩展欧几里德算法 原理: 令d=gcd(a,b),原方程有整数解当且仅当d|c bx+(a%b)y=1 = ay+b(x-[a/b]*y)=1 解二元模线性方程 算法步骤: 整数a,b,c,设d=gcd(a,b) 在用欧几里德算法求gcd(a,b) 的过程中求方程 ax+by=d 的一组整数解: 若b=0,则x=1,y=0; 否则,递归调用gcd(b,a%b),可以得到bx+(a%b)y=d的解 x,y,令x=y,y=x-[a/b]y即满足ax+by=d 若d|c,设c=kd,则有a(kx)+b(ky)=c;否则原方程无整 数解 中国剩余定理 孙子定理,韩信点兵,隔墙算,鬼谷算,大衍求一 术... 物不知数 问题:今有物不知其数,三三数之剩 二,五五数之剩三,七七数之剩二,问物几何?答 曰:二十三.术曰:三三数之剩二,置一百四十, 五五数之剩三,置六十三,七七数之剩二,置三十, 并之,得二百三十三,以二百一十减之,即得.凡三 三数之剩一,则置七十,五五数之剩一,则置二十 一,七七数之剩一,则置十五,即得. --孙子算经 中国剩余定理 一般性问题:给定两两互质的正整数n ,n ,...,n , 1 2 k 要求找到最小的正整数a, 满足a≡a (mod n ) i i 算法步骤: