基础数论课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,*,2015,年信息学夏令营,*,基础数论,东营市胜利第一中学,高天宇,1,2015,年信息学夏令营,数论,数论是,OI,中一门神奇的分支。,有人爱它痴狂，有人恨它入骨。,无数,OIer,做数论题时发出了这样的感慨：,数论去死,不过大家不用担心,今天我们讲的都是比较简单的数论,让我们一起见识一下吧,2,2015,年信息学夏令营,约数与质数,3,2015,年信息学夏令营,欧几里得算法,算法用途：求两个数,a,b,的最大公约数,原理：如果用线段表示两个数字（一段就是最大公约数）,我们发现，大的数除以小的数得到的余数，仍然是最大公约数的倍数（图中画圈）,我们如果不停的用大的数除以小的数求余数。再递归求小的数和余数的最大公约数。直到余数为,0,时，小的数就是最大公约数。,4,2015,年信息学夏令营,欧几里得算法,试一试：,20,和,12,，,25,和,10,。,5,2015,年信息学夏令营,欧几里得算法,int gcd(int a,int b),if(!b)return a;,return gcd(b,a%b);,6,2015,年信息学夏令营,扩展欧几里得,7,2015,年信息学夏令营,扩展欧几里得,解决这个问题之前，我们首先来学习扩展欧几里得算法。,该算法用来求解方程,ax+by=gcd(a,b),，注意，这里的,x,和,y,不一定是正整数，也有可能是,0,或者负数。,8,2015,年信息学夏令营,扩展欧几里得,ax+by=gcd(a,b),边界情况：,当,b=0,时，,gcd(a,b)=a,，,x=1,y=0,9,2015,年信息学夏令营,扩展欧几里得,ax+by=gcd(a,b),假设,ax1,+by1=gcd(a,b);,假设,bx2,+(a%,b)y2=gcd(b,a%,b);,根据朴素的欧几里德原理有,gcd(a,b)=gcd(b,a%,b);,则,:ax1,+by1,=bx2+(a%,b)y2;,即,:ax1,+by1,=bx2,+(a-a/b*b)y2,=,ay2,+bx2,-a/bby2;,也就是,ax1,+by1=ay2+b(x2,-a/b*y2);,根据恒等定理得：,x1,=,y2;y1,=,x2,-a/b*,y2;,这样我们就得到了求解,x1,y1,的方法：,x1,，,y1,的值基于,x2,，,y2,。我们可以通过不断递归调用求解。,10,2015,年信息学夏令营,扩展欧几里得,void exgcd(int a,int b,int&d,int&x,int&y),if(!b)d=a;x=1;y=0;,else exgcd(b,a%b,d,y,x);y-=(a/b)*x;,11,2015,年信息学夏令营,扩展欧几里得,我们这样只能得出一组解，其他解呢？,如果我们现在有解（,x1,y1),，任取另外一组解,(x2,y2),，则有,ax1,+,by1,=,ax2,+,by2,=,gcd(a,b),变形可以得到,a(x1,x2),=,b(y2,y1),两边同时除以,gcd(a,b),得到,a(x1,x2),=,b(y2,y1),因为,(a,b)=1,，所以,(x1-x2),一定是,b,的倍数,取,x1-x2=kb,得,y2-y1=ka,12,2015,年信息学夏令营,扩展欧几里得,所以我们有以下结论：,对方程,ax+by+c=0,，一组整数解为,(x0,y0),，则它的任意整数解可以写成,(x0+kb,y0-ka),其中,a=a/gcd(a,b),，,b=b/gcd(a,b),13,2015,年信息学夏令营,扩展欧几里得,关于,ax+by=c,有没有解，我们有这么一个结论：,对于方程,ax+by=c,（,a,b,c,均为整数），如果,c,为,gcd(a,b),的倍数，则方程有整数解，反之无整数解。,证明：因为,a,和,b,都是,gcd(a,b),的倍数，所以,ax+by,一定也是,gcd(a,b),的倍数，如果,c,不是,gcd(a,b),的倍数，一定无解。,14,2015,年信息学夏令营,扩展欧几里得,15,2015,年信息学夏令营,唯一分解定理,任何一个大于,1,的自然数,N,，如果,N,不为质数，则,N,可以,唯一分解成,有限个质数的乘积。,这个定理用处大大的,分解质因数。可以用质数乘积的形式表示一些大数字，处理一类和约数有关的问题。,16,2015,年信息学夏令营,筛质数,Eratosthenes,筛法,复杂度,O(nlogn),欧拉筛法,复杂度,O(n),17,2015,年信息学夏令营,Eratosthenes,筛法,原理：所谓质数即没有除,1,和本身的因数。更进一步说，没有除自己以外的质因数。,所以，我们每确定出一个质数，就把所有该质数的倍数标记为,不是质数,就好像用一个筛子，把所有合数都筛下去,18,2015,年信息学夏令营,Eratosthenes,筛法,19,2015,年信息学夏令营,欧拉筛法,我们注意到，在,Eratosthenes,筛法中，有的数字被筛了好几次。如,12,就被,2,和,3,两个数字筛选。,如果我们采用一种筛法，保证每个合数只会被自己最小的质因子筛选，则我们可以得到一个复杂度,O(n),的算法（,n,指我们求,1n,范围内的质数）。,20,2015,年信息学夏令营,欧拉筛法,对于任意一个合数，我们可以拆成最小质数*某个数字的形式。我们枚举,某个数字,i,（区分与埃氏筛法的枚举质因数），然后再从第一个质数开始枚举，进行筛选。,为了保证每个合数只被最小质因数筛选，当我们枚举的质数可以整除,某个数字,时，如果再往大里枚举，枚举的质数就不可能是最小质数了。,21,2015,年信息学夏令营,欧拉筛法int cntprime=0;,for(int i=2;i=n;i+),if(!flagi)prime+cntprime=i;,for(int j=1;j=1),if(b&1),ans=(ans*a)%p;,return,ans;,32,2015,年信息学夏令营,质数快速判定,Miller-Rabbin,33,2015,年信息学夏令营,例题,34,2015,年信息学夏令营,巨大的斐波那契数,输入两个非负整数,a,b,和正整数,n,（,0=a,b264,1=n=1000),，你的任务是计算,f(ab),除以,n,的余数。其中,f(0)=f(1)=1,，且对于所有非负整数,i,，,f(i+2)=f(i+1)+f(i),。,35,2015,年信息学夏令营,巨大的斐波那契数,这么大的数字，直接算是不现实的。,此时我们会想，要是,f(i)%,n,能出现循环多好啊。,我们取,F(i)=f(i),%,n,。若,(F(i-1),F(i),出现重复，则整个序列将开始重复。,比如,n=3,时,1,，,1,，,2,，,0,，,2,，,2,，,1,，,0,，,1,，,1,，,2,，,0,，,2,，,2,因为余数最多有,n,种可能，所以最多到第,n2,项，就会出现重复，开始循环。,所以我们先花至多,O(n2),的时间处理一下找到循环节，再判断一下,F(ab),具体等于哪一项即可。,36,2015,年信息学夏令营,计算组合数,已知,C(n,m)=n!,/,(m!,(n,m)!,给定,p,q,r,s,（,=105),计算,C(p,q)/C(r,s),，保证输出结果小于,108,，保留,5,位小数,37,2015,年信息学夏令营,计算组合数,C(p,q),和,C(r,s),本身太大，无法直接计算！,遇到这种问题，通常都需要分解质因数。,首先预处理出,105,内所有的质数，将质数存储在数组,prime,中。用,ei,表示答案在分解质因数后有,primei,这个因子,ei,个。,例如数字,12,质因数分解为,2,*,2,*,3,下标,1,2,3,prime,2,3,5,e,2,1,0,38,2015,年信息学夏令营,计算组合数,分解质因数的方法：从小到大枚举质数，如果质数能整除当前数字，就除，一边除相应的数组,e,中的数字,+1,，直到数字变成,1,（举个栗子）。,10000,以内的质数不多，也就几百个，而且一个数的质因数最多有,logn,个。所以分解质因数的复杂度不高。,39,2015,年信息学夏令营,计算组合数,我们可以对于算式中的每个数字，边分解质因数边往,e,中,+,或者,-,。,如果数字在分子上，相当于乘法，将,e,中的数字对应,+,，如果在分母上，相当于除法，将,e,中的数字对应,-,。,举个例子：,C(5,3),/,C(2,4),40,2015,年信息学夏令营,最小公倍数的最小和,输入整数,n(1=n0,且,S,的值最小。,46,2015,年信息学夏令营,Min,先把问题简单化，取,n=2,取,s=x1,*,a1+x2,*,a20,最小,这个方程和我们之前讲的线性不定方程形式相同。形如,ax+by=c,的方程有个特点，如果,x,y,有整数解的话，必须满足：,gcd(a,b)|c,反过来，,ax+by,的正数最小值是,gcd(a,b),47,2015,年信息学夏令营,Min,当推广到,n2,的情况，上面的结论也是成立的。对于,S=A1*X1+.An*Xn,，它的正数最小值等于,gcd(A1,A2,An),证明方法和我们证明,ax+by=c,对该结论成立的方法类似。,最后我们只需要求一下,A1,An,的,gcd,即可。,48,2015,年信息学夏令营,乘法原理和加法原理,做一件事情有,n,个办法,每个办法,pi,个方案,则一共有,p1+p2+.+pn,种方案。,做一件事情有,n,个步骤,每个步骤有,pi,个方案,则一共有,p1*p2*.*pn,种方案。,49,2015,年信息学夏令营,排列组合,A(n,m),表示,n,个东西里面选出,m,个东西排列的方案数,A(n,m)=n,*,(n-1)*(n-2)*,*(n-m+1),=n!/(n-m)!,C(n,m),表示,n,个东西里面选出,m,个东西的方案数,C(n,m)=A(n,m)/A(n,n)=n!/m!(nm)!,组合数性质,1,：,C(n,m)=C(n-1,m-1)+C(n-1,m),可以用在预处理组合数的值上。,组合数性质,2,：,C(n,m)=C(n,n-m),50,2015,年信息学夏令营,排列组合：小团体问题,例,1,：,4,个男生，,3,个女生，高矮互不相等，现在将他们排成一行，要求从左到右，女生从矮到高排列，有多少种排法？,先定位后定序,，首先我们可以先确定哪些位置是男生的，哪些位置是女生的。,C(7,4),然后我们再确定男生和女生各自的排列顺序。对于女生，因为从矮到高排列，所以只有一种排列方式。对于男生，一共有,P(3,3),种排列方式,所以最后的答案是：,C(7,4),*,P3,3),51,2015,年信息学夏令营,排列组合：插板法,例,2,：一共有,n,个相同的物品，放到,m,个不同的盒子里面，每个盒子里面至少放一个物品，请问一共有几种方案？,因为,n,个物品没有区别，我们可以先把他们平铺开,分装到,m,个盒子里面，相当于把这排列成一行的,n,个元素分成,m,部分，只要插入,m-1,个板子把它们隔开就可以,52,2015,年信息学夏令营,排列组合：插板法,比如,n=8,m=4,如何转换成排列组合？,如果有,n,个元素，就会有,n-1,个缝隙，,m,个盒子，就会有,m-1,个板子。相当于,n-1,个缝隙中挑选,m-1,个插入板子。答案等于,C(n-1,m-1),53,2015,年信息学夏令营,排列组合：插板法,例,3,：在例,2,的基础上，我们不限制每个盒子里面装的物体的数量。即每个盒子可以一个物体都不装。,刚才所讲的插板法只能处理每个盒子至少装一个物体的问题，这该怎么办？,我们可以多加上,m,个虚拟物体，每个盒子里面提前先放上一个，这样问题就转换成,一共有,n+m,个物体，,m,个盒子，每个盒子里面至少放,1,个，一共有多少种放法？,答案是,C(n+m-1,m-1),54,2015,年信息学夏令营,排列组合：三角形,BZOJ3505,CQOI2014 同学同时学数学和化学，,2,个同学同时学信息和化学，,1,个同学三者都学。问一共有几个学竞赛的同学答案是,14+20+12-4-3-2+1,4,20,14,12,3,2,1,63,2015,年信息学夏令营,容斥原理,64,2015,年信息学夏令营,二项式定理,65,2015,年信息学夏令营,期望与概率,期望指试验中每次可能结果的概率乘以其结果的总和。它反映随机变量平均取值的大小，记作,E(X),。,如，一个人去抽奖，抽不到奖的概率是,99.9%,，抽到一百万的概率是,0.1%,，则他得到的奖金的期望是,E(X)=0,*,99.9%+1000000,*,0.1%=1000,。,也就是说，他去抽奖平均将得到,1000,块钱。,66,2015,年信息学夏令营,期望与概率,期望的性质：,若,C,为常数,E(CX)=CE(X),，如语文分数乘,100,的期望与语文分数期望乘,100,是一样的。,E(X+Y)=E(X)+E(Y),，如语文,+,数学分数的期望与语文分数期望和数学分数期望是一样的。,当,X,，,Y,互相独立（不影响）时,E(XY)=E(X)E(Y),，如当语文数学成绩互相不影响的时候，语文*数学成绩的期望，等于语文成绩的期望*数学成绩的期望,67,2015,年信息学夏令营,条件概率,68,2015,年信息学夏令营,THANKS,FOR,LISTENING!,69,2015,年信息学夏令营,