acm中的数学问题数论部分省公开课一等奖全国示范课微课金奖课件

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

：a|b=>a|bc性质3

：

a|b,a|c=>a|kb±lc性质4：

a|b,b|a=>a=±b第11页整除基本性质性质5：a=kb±c=>a,b公因数与b,c公因数完全相同证实：假设d是b,c公因数，即d|b,d|c。利用整除性质3，d整除b,c线性组合，故d|a。所以d是a,b公因数反之，假如d是a,b公因数，也能证出d是b,c公因数第12页第一部分同余相关整除基本性质欧几里德算法扩展欧几里德算法中国剩下定理第13页请写出12，30共有约数第14页请写出12，30共有约数 1,第15页请写出12，30共有约数 1,2,第16页请写出12，30共有约数 1,2,3,第17页请写出12，30共有约数 1,2,3,6.第18页最大条约数与最小公倍数最大条约数定义：两个或若干个整数条约数中最大那个条约数例子：12，30最大条约数怎样求两个整数最大条约数：辗转相除法（扩展版）Stein算法第19页请写出12，10共有倍数第20页请写出12，10共有倍数60,第21页请写出12，10共有倍数60,120,第22页请写出12，10共有倍数60,120,180,第23页请写出12，10共有倍数60,120,180,240…第24页最大条约数与最小公倍数最小公倍数定义：两个或若干个整数共有倍数中最小那一个。例子：12，10最小公倍数最大条约数与最小公倍数关系lcm(a,b)*gcd(a,b)=a*b全部公倍数都是最小公倍数倍数，全部条约数都是最大条约数约数。第25页欧几里德算法欧几里德算法(TheEuclideanAlgorithm)又称辗转相除法

或者短除法原理:gcd(a,b)=gcd(b,amodb)证实：利用整除性质5(a=kb±c=>a,b公因数与b,c公因数完全相同)辗转相除直到两数整除，其中除数就是要求最大条约数。第26页欧几里德算法例子：利用欧几里德算法，求63与81最大条约数步骤：a=81,b=63,amodb=18a←63,b←18,amodb=9a←18,b←9,amodb=0所以9就是63与81最大条约数第27页欧几里德算法欧几里德算法:whileb>0

dor←a%ba←bb←rreturna第28页欧几里德算法欧几里德算法是计算最大条约数传统算法,也是最简单算法,效率很高时间复杂度:O(lgn)(最坏情况:斐波那契数列相邻两项)空间复杂度:O(1)不过,对于大整数来说,取模运算非常耗时第29页欧几里德算法时间复杂度:最坏情况为斐波那契数列相邻两项体会(13,8)，(12,8)a=k*b+c,c=a-k*b同时满足下面两个条件，序列递减得最慢，即辗转相除法次数最多k=1最大条约数为1第30页Stein算法原理:gcd(ka,kb)=k*gcd(a,b)当k=2时,说明两个偶数最大条约数必定能被2整除当k与b互素时，gcd(ka,b)=gcd(a,b)当k=2时，说明计算一个偶数和一个奇数最大条约数时，能够先将偶数除以2(a,b)=(b,a-b)第31页Stein算法例子：两个都为偶数(10,8)=2*(5,4)一个奇数，一个偶数(15,12)=

(15,6)两个都是奇数(25,15)=(15,5)第32页Stein算法Stein算法(假设0<=b<a):

r←0

whileb>0

doifa偶,b偶thena←a>>1b←b>>1r←r+1 elseifa偶,b奇thena←a>>1 elseifa奇,b偶thenb←b>>1 elseifa奇,b奇thena←(a-b)>>1

ifa<bthen交换a,b returna<<r第33页Stein算法关键精华：两个大数最大条约数转化为两个较小数最大条约数时间,空间复杂度均与欧几里德算法相同最大优点:只有移位和加减法计算,防止了大整数取模运算第34页第一部分同余相关整除基本性质欧几里德算法扩展欧几里德算法中国剩下定理第35页扩展欧几里德算法例子：利用欧几里德算法，求63与81最大条约数第36页扩展欧几里德算法原理：对于不完全为0非负整数a，b，必定存在整数对x，y，使得gcd(a，b)=ax+by。a=kb+c,c=a–kb在用欧几里德算法求解最大条约数过程中，将每一步余数都表示为原始两个数线性组合形式。最大条约数就是欧几里德算法中，最终不为0那个余数第37页扩展欧几里德算法扩展欧几里德算法(递归实现):

intgcd(inta,intb) ifb=0 thenx←1y←0 returna d←gcd(b,a%b) x'←yy'←x-[a/b]y x←x'y←y' returnd第38页扩展欧几里德算法不但能求得最大条约数，还能求得关于原始两个数线性组合。第39页解二元模线性方程例子：解方程15x+12y=35x+4y=1(1,-1)解方程15x+12y=65x+4y=2(1,-1)*2解方程15x+12y=1gcd(15,12)=3，所以原方程无解第40页解二元模线性方程二元模线性方程：形如ax≡c(modb)或ax+by=c其中a,b,c,x,y均为整数原理:令d=gcd(a,b),原方程有整数解当且仅当d|c扩展欧几里德算法第41页解二元模线性方程解二元模线性方程普通步骤约分到最简形式找到初始解（扩展欧几里德算法）加上或者减去两个系数最小公倍数关于这两个系数约数，也是这个方程解第42页第一部分同余相关整除基本性质欧几里德算法扩展欧几里德算法中国剩下定理第43页中国剩下定理同模情况下，有这么性质：乘法标准8mod7=1加法标准8mod7=110mod7=318mod7=416mod7=264mod7=8mod7第44页中国剩下定理在0–14之间找到一个数，使得这个数除以3余1，除以5余2。经求解该数为7，而且该数唯一。若不限定在0–14之间，那么这么数为7，22，37，52…两个数之间相差3与5最小公倍数15第45页中国剩下定理"物不知数"问题抽象表示:x≡2(mod3)x≡3(mod5)x≡2(mod7)求满足上述条件最小正整数x第46页中国剩下定理"物不知数"问题抽象表示:x≡2(mod3)x≡3(mod5)x≡2(mod7)求满足上述条件最小正整数x“物不知数”问题标准解法:3k1+1,

5k2,7k3（70）3k1，5k2+1,7k3（21）3k1，5k2,7k3+1（15）x=70*2+21*3+15*2=233x=233–2*[3,5,7]=23第47页中国剩下定理普通性问题:给定两两互质正整数n1,n2,...,nk,要求找到最小正整数a,满足a≡ai(modni)将问题分解成若干次求解二元模线性方程组解用扩展欧几里德算法求解二元模线性方程第48页中国剩下定理算法步骤:令n=n1n2...nk,mi=n/ni利用扩展欧几里德算法计算出xi满足mixi≡1(modni),因为n1,n2,...,nk两两互质,必有gcd(mi,ni)=1,即可确保一定有解则a≡a1x1m1+a2x2m2+...+akxkmk(modn)第49页中国剩下定理经典应用:大整数表示选取两两互素正整数n1,n2,...,nk求解对每个ni取模值ri,这个余数组就能够唯一确定一个1~n1n2...nk大整数做大整数加,减,乘法时,只要确保在这个范围内,均可转化为分别对对应余数进行计算第50页数论题目推荐2342、1528、1953(都是赤裸裸)进阶题目：POJ1091、POJ1619、POJ1845、POJ2478、POJ2480、POJ2603、POJ2649、POJ2773、POJ2992、POJ3292第51页第二部分素数相关算术基本定理欧拉定理素数测试Pollardrho方法第52页关于互素性质a与b,c同时互素，则a与b*c也互素p为素数，p|b*cp|borp|ca*b|cand(a,c)=1b|cak与b互素(k>=1)，则a与b也互素a≡1(modb)，则a与b互素第53页筛法目标:求出n以内全部质数算法步骤:初始时容器内为2到n全部正整数取出容器中最小数p,p一定是质数,删去p全部倍数(注:只需从p2开始删除即可)重复上述步骤直到容器为空第54页筛法优点:算法简单,空间上只需要一个O(n)bool数组缺点:一个数可能被重复删去屡次,影响效率例:在p=2,3,5,7时均会尝试删除210普通,若x有k个质因子,则x会被处理k次第55页筛法(改进)改进:初始时容器内为2到n全部正整数取出容器中最小数p,p一定是质数删去全部pi,令q为第一个未被删除数,保留q,删去全部piq,再令q为下一个未被删除数...直到q遍历全部未被删除数为止(这一步骤能够把最小质因数为p全部数删去)重复上面两个步骤直到容器为空第56页筛法(改进)用bool数组+双向链表实现,空间复杂度仍为O(n)小优化:初始时只加入奇数第57页算术基本定理任何一个大于1自然数n,都能够唯一分解成有限个质数乘积n=p1r1p2r2...pkrkp1<p2<...<pk均为质数,r1,r2,...rk均为正整数第58页欧拉函数记φ(x)为与x互质且小等于x正整数个数设x=p1r1p2r2...pkrkφ(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|x若p2|x,则φ(x)=φ(x/p)*p不然φ(x)=φ(x/p)*(p-1)第59页欧拉函数证实:若p为质数,则φ(p)=p-1φ(pr)=pr(1-1/p)=p(r-1)(p-1)若a,b互质,则φ(ab)=φ(a)φ(b)扩展:n全部因子之和

(p10+...+p1r1)(p20+...+p2r2)...(pk0+...+pkrk)第60页欧拉定理若a和m互质,则aφ(m)≡1(modm)证实:设φ(m)个正整数r1,r2,...,rφ(m)满足:ri与m互质,对于任意i≠j,ri≠rj(modm)因为a与m互质,能够证实ar1,ar2,...,arφ(m)依然满足上述条件这么就有(ar1)(ar2)...(arφ(m))

≡r1r2...rφ(m)(modm)而(ar1)(ar2)...(arφ(m))

≡aφ(m)r1r2...rφ(m)(modm)两边同时约去r1r2...rφ(m)即得到欧拉定理第61页素数测试费马小定理:若p为素数,则对于任意小于p正整数a,有a(p-1)≡1(modp)证实:欧拉定理特例(m为质数)问题:只是必要条件,不是充分条件反例:561,1105,1729...第62页素数测试二次探测定理:若p为素数,a2≡1(modp)小于p正整数解只有1和p-1满足费马小定理和二次探测定理数能够确定是素数第63页Miller-Rabin算法Miller-Rabin算法(n为待判定数):令n-1=m*2j,m为奇数随机在2~(n-1)之间取一个整数b,令v=bm对v平方,当v=1时,若上一次v既不是1也不是(n-1),由二次探测定理,n不是素数,退出