资源描述：
《2010北大acm暑期讲义数学题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ACM中的数学问题北京大学ACM竞赛队队员林舒引言在ACM竞赛中,经常可以看到数学问题的身影可以是纯数学问题,也可以是需要利用数学上的一些公式,定理,算法来辅助解决的问题会者不难,而不会的人在赛场上一般很难推出公式或进行证明往往想起来费劲,写起来却很轻松常见的数学问题数论组合数学博弈论线性代数高等数学线性规划概率论...本讲内容简单数论Polya定理SG函数与矩阵有关的问题本讲内容基本上是最基础的,同时也是ACM竞赛中最常用的数学算法一些数学定理,公式的简略证明或推导,从而加深对它们的理解和认识,也方便记忆往届ACM竞赛中的数学问题数论简而
2、言之,数论是研究整数的理论在ACM竞赛中,经常用到数论的相关知识纯数论的题目不多,大部分是和其他类型的问题结合起来的约数,倍数,模线性方程,欧拉定理,素数整除的性质性质1:a
3、b,b
4、c=>a
5、c性质2:a
6、b=>a
7、bc性质3:a
8、b,b
9、c=>a
10、kb±lc性质4:a
11、b,b
12、a<=>a=±b性质5:a=kb±c<=>a,b的公因数与b,c的公因数完全相同(利用性质3)最大公约数最小公倍数欧几里德算法(辗转相除法,短除法)原理:若a≡r(modb),则gcd(a,b)=gcd(b,r)(利用性质5证明)算法步骤(递归实现):整数a,b,假设a>b若b
13、=0,则gcd(a,b)=
14、a
15、;否则gcd(a,b)=gcd(b,a%b)最小公倍数:lcm(a,b)=a*b/gcd(a,b)解二元模线性方程二元模线性方程(二元一次不定方程):形如ax≡c(modb)或ax+by=c扩展欧几里德算法原理:令d=gcd(a,b),原方程有整数解当且仅当d
16、cbx+(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),可
17、以得到bx'+(a%b)y'=d的解x',y',令x=y',y=x-[a/b]y'即满足ax+by=d若d
18、c,设c=kd,则有a(kx)+b(ky)=c;否则原方程无整数解中国剩余定理孙子定理,韩信点兵,隔墙算,鬼谷算,大衍求一术..."物不知数"问题:"今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?答曰:'二十三.'术曰:三三数之剩二,置一百四十,五五数之剩三,置六十三,七七数之剩二,置三十,并之,得二百三十三,以二百一十减之,即得.凡三三数之剩一,则置七十,五五数之剩一,则置二十一,七七数之剩一,则置十五,即得."--孙子算经中国剩余定理一般性
19、问题:给定两两互质的正整数n1,n2,...,nk,要求找到最小的正整数a,满足a≡ai(modni)算法步骤:令n=nn...n,m=n/n12kii显然gcd(m,n)=1,利用扩展欧几里德算法计算出xiii满足mx≡1(modn)iiia≡a1x1m1+a2x2m2+...+akxkmk(modn)筛法目标:求出n以内的所有质数算法步骤:初始时容器内为2到n的所有数取出最小的数p,p一定是质数,删去p的所有倍数(注:只需从p2开始删除即可)重复上述步骤直到容器为空用bool数组实现即可缺陷:一个数可能被重复删去多次,影响效率筛法改进:初始时容器内为
20、2到n的所有数取出最小的数p,p一定是质数删去所有的pi,令q为第一个未被删除的数,保留q,删去所有的piq,再令q为下一个未被删除的数,删去所有的piq...直到q遍历所有未被删除的数为止(这一步骤可以把最小质因数为p的所有数删去)重复上面两个步骤直到容器为空用bool数组+双向链表实现小优化:初始时只加入奇数算术基本定理任何一个大于1的自然数n,都可以唯一分解成有限个质数的乘积n=pr1pr2...prk12kp21、kφ(x)=x*(1-1/p1)*(1-1/p2)*...*(1-1/pk)或φ(x)=p1(r1-1)(p1-1)p2(r2-1)(p2-1)...pk(rk-1)(pk-1)递推式:质数p满足p
22、x,若p2
23、x,则φ(x)=φ(x/p)*a,否则φ(x)=φ(x/p)*(a-1)欧拉函数证明:若p为质数,则φ(p)=p-1φ(pr)=pr(1-1/p)=p(r-1)(p-1)若a,b互质,则φ(ab)=φ(a)φ(b)扩展:n的所有因子之和(p0+...+pr1
