资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数论,目录,数论相关知识及其基本算法,自然数和整数,整除,最大公约数和最小公倍数,同余,素数,数论解题样例,自然数和整数,自然数,有一个起始的自然数,0,；,任何一个自然数都有后继；,0,不是任何自然数的后继；,不同的自然数有不同的后继；,存在一组与自然数有关的命题。假设此命题对起始的自然数,0,成立，如果该命题对任一自然数成立可以推导出对其后继也成立，则此命题对所有自然数都成立。,整数,负整数与自然数一起构成整数,整除,一个整数,a,能被另一个整数,d,整除，记做,d|a,，,意味着存在某个整数,k,，有,a=,kd,。,如果,a,0,且,d|a,，则,IdI,0,则,称,d,是,a,的约数（,Divisor,）；,一个整数,a,的约数最小为,1,，最大为,IaI,，,每个整数,a,都可被其平凡约数,1,和,a,整除；,a,的非平凡约数也称为,a,的因子（,Factor,）；,例：,30,的约数为,1,，,3,，,5,，,6,，,10,，,15,，,30,，其中,3,，,5,，,6,，,10,，,15,为,30,的因子,整除,整除的性质,如果,d|a,，则对于任意整数,k,有,d|ka,如果,d|a,且,d|b,，则,d|(a,b,),如果,b|a,且,a|b,，则,a=b,如果,a|b,且,b|c,，则,a|c,整除关系具有传递性，由于它显然也具有自反性和反对称性，所以它是一个偏序关系。,整除,几种特殊的整除的例子,若,2,能整除,a,的最末位，则,2|a,；若,4,能整除,a,的最后两位，则,4|a,；若,8,能整除,a,的最末三位，则,8|a,；,若,5,能整除,a,的最末位，则,5|a,；若,25,能整除,a,的最后两位，则,25|a,；若,125,能整除,a,的最末三位，则,125|a,；,整除,若,3,能整除,a,的各位数字之和，则,3|a,；若,9,能整除,a,的各位数字之和，则,9|a,若,11,能整除,a,的偶数位数字之和与奇数位数字之和的差，则,11|a,最大公约数,公约数,如果,d,是,a,的约数并且也是,b,的约数，则,d,是,a,与,b,的公约数,(Common Divisor),1,是任意两个整数的公约数,最大公约数（,Greatest Common Divisor,）,所有公约数中最大的一个，记做,gcd(a,b,),最大公约数,最大公约数的性质：,gcd(a,ka,)=|a|,对任意整数,a,与,b,，如果,d|a,且,d|b,，则,d|gcd(a,b,),对所有整数,a,和,b,以及任意非负整数,n,，,gcd(an,bn,)=,ngcd(a,b,),对所有正整数,d,a,和,b,，如果,d|ab,并且,gcd(a,d,)=1,，则,d|b,如果,q,和,r,是,a,除以,b,的商和余数，即,a=,bq+r,，则,gcd(a,b,)=,gcd(b,r,),最大公约数,另一种不用除法的,gcd,算法（,a=b),1),若,a=b,则,gcd(a,b,)=a;,2,）若,a,b,均为偶数，则,gcd(a,b,)=2xgcd(a/2,b/2);,3),若,a,为偶数,b,为奇数,则,gcd(a,b,)=gcd(a/2,b);,4,）若,a,b,均为奇数，则,gcd(a,b,)=,gcd(a-b,b,);,最小公倍数,公倍数,如果,m,是,a,的倍数并且也是,b,的倍数，则,m,是,a,与,b,的公倍数,最小公倍数,所有公倍数中最小的那个，记做,lcm(a,b,),最小公倍数的性质,lcm(a,b,)=a*,b/gcd(a,b,),辗转相除法求最大公约数,原理,如果,q,和,r,是,a,除以,b,的商和余数，即,a=,bq+r,，则,gcd(a,b,)=,gcd(b,r,),举例,gcd(1001,767)=gcd(767,234)=gcd(234,65)=gcd(65,39)=gcd(39,26)=gcd(26,13)=gcd(13,0)=13,代码,辗转相除法求最大公约数,/,要求,a,b,不同时为,0,int,gcd(,int,a,int,b) ,if,(b = 0) ,return,a;,return,gcd(b, a % b);,利用最大公约数求最小公倍数,int,lcm(,int,a,int,b) ,if,(a * b = 0) ,return,0;,return,a * b /,gcd(a, b);,同余,同余,设,m,是正整数，,a,b,是整数，如果,m|(a-b,),，则称,a,和,b,关于模,m,同余，记作,ab(mod,m),或者说，如果,a,b,除以,m,的余数相等，则称,a,和,b,关于模,m,同余,同余的性质,aa(mod,m),如果,ab(mod,m),，则,ba(mod,m),如果,ab(mod,m),且,bc(mod,m),，,ac(mod,m),如果,ab(mod,m),且,cd(mod,m),，则,acb,d(mod,m),，,acbd(mod,m),同余,同余的性质,(cont.),如果,ab(mod,m),，则,a,n,b,n,(mod,m),，,nN,如果,acbc(mod,m),，则,ab(mod,(,m/gcd(c,m,),如果,ab(mod,m),且,d|m,，则,ab(mod,d),如果,ab(mod,m),，则,adbd(mod,m),如果,ab(mod,m,i,),，,i=1,2,n,，,l=lcm(m,1,m,2,m,n,),，则,ab(mod,l),如果,p,为素数，则,a,p,a(mod,p),；如果,gcd(a,p,)=1,，则,a,p-1, 1(mod p),素数和合数,素数,自然数中，除了,1,之外，只能被,1,和该数自身整除的数,大于,1,的正整数,，如果仅有的正因子是,1,和,则称,为素数（,prime,）。大于,1,又不是素数的正整数称为合数（,compound,）。如果,n,是合数，那么,n,必有一个小于或等于,sqrt(n,),的素因子。,素数和合数,其他,-,2,是最小的素数,2,是唯一一个偶素数,算术基本定理,每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的“乘积”可以有,0,个、,1,个或多个素因子）。,筛法求素数,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,代码（筛法求素数）,const,int,MAX = 10000;,bool,primeMAX,+ 1;,void,searchprime,() ,memset(prime,true,sizeof(prime,);,prime1 =,false,;,代码（筛法求素数）,for,(,int,i = 2,; i = (,int,),floor(sqrt(MAX,);,+i,) ,if,(,primei,) ,int,j = i * 2;,while,(j = MAX) ,primej, =,false,;,j += i;,素数的判定,原始的判定方法，根据素数的定义,改进的判定方法,1,，,x,可以分解为两个整数,a,b,的积，即,x=a*b,，,ab,，那么,a ,sqrt(x,),改进的判定方法,2,，其实,2,到,x,的平方根中那些合数也是没有必要用来判断的。如果事先生成一个素数表，循环的次数还可以降低。利用素数表来求解。,代码（原始的素数判定方法）,bool,isPrime(,int,x) ,for,(,int,i = 2; i x; +i) ,if,(x % i = 0) ,return,false,;,return,true,;,代码（改进的素数判定方法,1,）,bool,isPrime(,int,x) ,for,(,int,i = 2; i =,(,int,),floor(sqrt(x,),; +i) ,if,(x % i = 0) ,return,false,;,return,true,;,代码（改进的素数判定方法,2,）,bool,isPrime(int,x) ,int,i = 0;,/ list,是预先生成好的素数表,while (,listi, *,listi, 1,），若存在自然数,M,和,N,（,MN,），使得,K,M,和,K,N,均大于或等于,1,000,，且它们的末尾三位数相等，则称,M,和,N,是一对“,K,尾相等数”。,求,M+N,值最小的,K,尾相等数。,K,尾相等数,问题分析,对于一个数，它的幂是无穷无尽的，但是我们可以注意到末尾三位数只有,1,000,个，也就是表明一定会有重复的末尾三位数，当一个数的末尾三位数一定时，它的下一次幂的末尾三位数也一定了。也就是说当第一次重复出现大于等于,1,000,的末尾三位数时，这就是我们要求的,M,和,N,。,K,尾相等数,要注意的问题,K,M,和,K,N,要大于或等于,1,000,25: 25 625 15625 390625,对应的末位：,25 625,625,625,K,要做预处理,K mod 1000,1025,：,1025 1050625 1103812890625 1159693418212890625,对应的末位：,25 625,625,625,K,尾相等数,程序实现,int,i,j,k,n,p1,i1,ti,bj;,int,time1001;,K,尾相等数,程序实现,int,main() ,cin, n;,memset(time, 0,sizeof(time,);,i = n;,k = 1;,j = 0;,ti,= 0;,bj,= 0;,K,尾相等数,程序实现,if,(i = 1000) ,bj,= 1;,i = i % 1000;,do ,ti,=,ti,+ 1;,k = i * k;,K,尾相等数,程序实现,if,(k = 1000 |,bj,= 1),k = k,%,1000;,if,(,timek, = 0),timek, =,ti,;,else,j = k;,bj,= 1;,while (j = 0);,cout,timej, +,ti,;,return 0;,3n+1,数链问题,有这样一个问题，如下：,输入一个正整数,n,；,如果,n=1,则结束；,如果,n,是奇数则,n,变为,3*n+1,，否则,n,变为,n/2,；,转入第,2,步。,例如对于输入的正整数,22,，则数列为：,22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1,对于任意一个正整数，经过以上算法最终会推到,1,。对于给定的正整数,n,，我们把显示出来的数的个数定义为,n,的链长，例如,22,的链长为,16,。,对于任意一对正整数,i,和,j,，求,i,、,j,之间的最长链长。,3n+1,数链问题,问题分析,这是一道很简单的题目，无大多其他的技巧，只需要按照题目的要求一步步做下去即可。对于每一个正整数，可以很容易求得它的数链长度。,3n+1,数链问题,要注意的问题,i,、,j,之间包括,i,和,j,题目的例子,i=1, j=10,进一步的优化,记录下,1,至,10000,所有的链长,1,2,3,4,5,6,7,8,9,10,1,2,8,3,6,9,17,4,20,7,3n+1,数链问题程序实现,int,a, b,maxlen,;,int,linklen(int,x) ,int,l = 1;,while,(x != 1) ,+l;,if,(x /,如果,X,为奇数，则,X=3X+1,else,x = x / 2; /,如果,X,为偶数，则,X=X/2,return l;,3n+1,数链问题程序实现,void run ,int,i, l;,for,(i = a; i ,maxlen,),maxlen,= l;,3n+1,数链问题程序实现,int,main() ,freopen(“LINK.IN,”, “r”,stdin,);,freopen(“LINK.OUT,”, “w”,stdout,);,cin, a b;,maxlen,= 0;,run();,cout, 0) ,+,len,;,alen, = n1,%,r1;,n1 =,n1,/ r1;,负权数,程序实现,/,以下是将,|N|,的,|R|,进制形式转化成,N,的,R,进制形式，具体数学原理见式,if,(n 0) p = 1;,else,p = 0;,while,(p 0) ,/,向,AP+1,位进,1,+ap+1;,i = p + 1;,负权数,程序实现,/,进位,while,(,ai, = r1) ,ai, -= r1;,+i;,+,ai,;,负权数,程序实现,/,若进位导致长度增加则更新长度,if,(i ,len,),len,= i;,ap, = r1 -,ap,;,p += 2;,负权数,程序实现,/,打印,void,print() ,int,i;,for,(i =,len,; i = 0; -i) ,if,(,ai, 10),cout,ai,;,else,cout, (char) (,ai, + 55);,cout, n r) ,/,无论在什么进制，,0,仍是,0,if,(n = 0),cout, 0 X2+X 1 1 -X+1 - 1 1 0XOR 1 1 0- 1 0 1 0 -X3+X,质多项式,问题分析,(X3+X) / (X+1) = X2+X,1 1 0 -1 1 / 1 0 1 0XOR 1 1 - 1 1 0XOR 1 1 0 - 0,质多项式,问题分析,(X7+X5+X3+X2+X+1) / (X4+X3+X+1),1 1 0 1 -1 1 0 1 1 / 1 0 1 0 1 1 1 1 XOR 1 1 0 1 1 - 1 1 1 0 1 XOR 1 1 0 1 1 - 1 1 0 1 1 XOR 1 1 0 1 1 - 0,质多项式,需要注意的问题,除了次数为,1,的情况，质多项式都包含常数项,1,；,系数只能为,0,和,1,的,n,次多项式共有,2,n,个；,从素数得到的经验：,n,次质多项式不止一个,第一个,n,次质多项式离,x,n,不会太远,质多项式程序实现,int,bin31;,int,k, now, i;,bool,flag;,质多项式程序实现,int,weight(int,w) ,int,i;,for,(i = 30; i = 0; -i) ,if,(,bini, = w) ,return i;,质多项式程序实现,/,多项式除法,bool,divide(int,a,int,b) ,int,wa,wb,;,wa,=,weight(a,);,wb,=,weight(b,);,b = b,=,wb,) ,a = b;,while,(,binwa, a) ,-,wa,;,b = 1;,return (,wa,=,wb,);,质多项式程序实现,void,init() ,int,i;,bin0 = 1;,for,(i = 1; i = 30; +i) ,bini, =,bini,- 1 * 2;,质多项式程序实现,void,print(int,p) ,int,i;,if,(k = 1) ,cout, x = 1; -i) ,if,(,bini, = p) ,p -=,bini,;,cout, “x” i +;,cout, 1 k;,质多项式程序实现,while,(k != 0) ,now =,bink, - 1;,do,now += 2;,flag = true;,for,(i = 2; i k;,return 0;,猴子舞,(,选讲,),猴子舞是由,N,只猴子同时进行的。开始时，地上有,N,个圆圈，每个圆圈上站了一只猴子。地上还有,N,个箭头，每个圆圈恰好是一个箭头的起点和另一个箭头的终点，并且没有一个圆圈同时是某个箭头的起点和终点。表演开始时，所有的猴子同时按它所站的圆圈的箭头的方向跳到另一个圆圈中，这作为一步。当所有的猴子都回到自己原来所站的圆圈时，表演便结束了。,求对于,N,可以达到的最大步数。,猴子舞,问题分析,建模,给定一个正整数,N,，要求若干个数,A,1,A,2,A,m,(A,1,+A,2,+A,m,=N),，满足不存在,B,1,B,2,B,p,(B,1,+B,2,+B,p,=N),，使得,lcm,(B,1,B,2,B,p,),lcm,(A,1,A,2,A,m,),猴子舞,问题分析,搜索法,枚举所有可能的分解方式，求,lcm(,最小公倍数）,搜索范围比较大,lcm,需要用到高精度乘法,猴子舞,问题分析,搜索剪枝,N=A,1,+A,2,+A,m,，如果,A,i,=,A,j,，显然其中一个对最小公倍数没有贡献，所以要求,A,i,A,j,；,优先考虑,A,i,是素数的情况，如果,Ai,是互不相同的素数，对,lcm,的贡献很大的；,保证,A,i,之间是互质的，因为如果,Ai,、,Aj,不互质会浪费掉部分分解，当,A,i,之间互质时，计算,lcm,时把,Ai,相乘即可；,猴子舞,需要注意的问题,不能有长度为,1,的圈,猴子舞,程序实现,const,int,MAXN = 300;,typedef,int,TArray100;,struct,TLongint,int,len,;,TArray,data;,;,猴子舞,程序实现,int,nl,sk, num;,TArray,list, index,sindex,;,TLongint,max;,猴子舞,程序实现,/,比较两高精度数的大小,bool,bigger(TLongint,i1,TLongint,i2) ,int,pos;,if,(i1.len != i2.len) ,return (i1.len i2.len);,猴子舞,程序实现,pos = i1.len - 1;,while,(pos = 0 & i1.datapos = i2.datapos) ,-pos;,if,(pos i2.datapos);,猴子舞,程序实现,/,乘数在,integer,范围内的高精度乘法,void,longmul(TLongint,&m,int,n) ,int,i, c;,c = 0;,for,(i = 0; i = m.len-1; +i) ,c +=,m.datai, * n;,m.datai, = c % 10;,c /= 10;,猴子舞,程序实现,while,(c != 0) ,m.datam.len, = c % 10;,c /= 10;,+,m.len,;,猴子舞,程序实现,/,求一定范围内,(=MAXN),的素数,void,getprimes,() ,int,i, j;,bool,flag;,memset(list, 0,sizeof(list,);,list0 = 6; list1 = 2;,nl,= 2;,猴子舞,程序实现,for,(i = 3; i = MAXN; +i) ,flag = true;,for,(j = 1; j =,nl,- 1; +j) ,if,(i %,listj, = 0) ,flag = false;,break;,猴子舞,程序实现,if,(flag) ,listnl, = i;,+,nl,;,listnl, = MAXN;,猴子舞,程序实现,/,对目前的搜索方案计算可以得到的步数,void,checkresult(int,remain,int,k) ,TLongint,res;,int,i, j;,if,(remain = 1) return;,memset(res, 0,sizeof(res,);,res.len,= 1;,res.data0 = 1;,猴子舞,程序实现,for,(i = 1; i 0) ,for,(j = 0; j 3) ,longmul(res, 2);,if,(index2 = 0 & remain % 2 = 1) ,longmul(res, 3);, else ,if,(index1 = 0),longmul(res, 2);,longmul(res, 3);,猴子舞,程序实现,if,(,bigger(res, max) ,max = res;,sindex,= index;,sk,= k;,猴子舞,程序实现,/,一般情况的搜索,void,findresult(int,num,int,k) ,int,val,;,val,=,listk,;,indexk, = 0;,猴子舞,程序实现,if,(,val, num) ,checkresult(num, k - 1);,return;,findresult(num, k+1);,+,indexk,;,if,(k 3) ,+,indexk,;,val,=,val,*,listk,;,猴子舞,程序实现,while,(,val, num) ,if,(num = 2 | num = 4) ,checkresult(num, k - 1);,return;,猴子舞,程序实现,findresult1(num, k + 1);,if,(k = 2) return;,+,indexk,;,if,(k = 1) ,+,indexk,;,val,=,val,*,listk,;,猴子舞,程序实现,while,(,val,= 0; -i) ,cout,max.datai,;,cout,= 6) ,index0 = 1;,index1 = 0;,index2 = 0;,if,(num 6) findresult1(num - 6, 1);,else,checkresult(0, 0);,printresult,();,猴子舞,程序实现,int,main() ,freopen(“DANCE.IN,”, “r”,stdin,);,freopen(“DANCE.OUT,”, “w”,stdout,);,getprimes,();,cin, num;,猴子舞,程序实现,while,(num 0) ,process(num,);,cin, num;,return 0;,数制转换,有一种数制的基数是,3,，权值可取,-1,0,1,，并分别用符号,-,0,1,表示，这种数制的,101,表示十进制数,10,，即,13,2,+03,1,+13,0,=10,，,这种数制的,-0,表示十进制数的,-3,，即,-13,1,+03,0,=-3,。,要求把给定的有符号整数转换为新数制的数。,数制转换,问题分析,证明存在性,整数,0,的新数制表示是,0,；整数,1,的新数制表示是,1,；整数,2,的新数制表示是,1-,；整数,-1,的新数制表示是,-,；整数,-2,的新数制表示是,-1,；,假设对一切,k,2,，对,|X|K,的所有命题,X,成立，以下证,K+1,和,-K-1,的新数制表示是存在的,K mod 3=0,，则由归纳假设,K/3,存在新数制表示,A,1,A,2,A,n,，则,K+1,存在新数制表示,A,1,A,2,A,n,1,K mod 3=1,，则由归纳假设,(K+2)/3,存在新数制表示,A,1,A,2,A,n,，则,K+1,存在新数制表示,A,1,A,2,A,n,-,K mod 3=2,，则由归纳假设,(K+1)/3,存在新数制表示,A,1,A,2,A,n,，则,K+1,存在新数制表示,A,1,A,2,A,n,0,同理,-K-1,也存在新数制表示,数制转换,问题分析,证明唯一性,设有新数制的两种表示,A,1,A,2,A,n,和,B,1,B,2,B,n,，不足,n,位的在前面用零补足。由新数制的定义可知：,3,n-1,A,1,+ 3,n-2,A,2,+ 3A,n-1,+A,n,= 3,n-1,B,1,+ 3,n-2,B,2,+ 3B,n-1,+B,n,上式两边对,3,取模可得,A,n,=,B,n,，于是有：,3,n-2,A,1,+ 3,n-3,A,2,+ A,n-1,= 3,n-2,B,1,+ 3,n-3,B,2,+ B,n-1,上式两边对,3,取模可得,A,n-1,=B,n-1,使用上述方法，通过有限步即得,A,i,=B,i,数制转换,问题分析,从个位开始到最高位逐位确定结果,输入,X,；,若为,0,则输出,0,并结束，否则下一步；,置结果符号串,S,为空；,若为,0,则输出,S,并结束，否则下一步；,若,X 0) ,if,(x,%,3 = 0) ,handle(x,/ 3);,cout, 0;,数制转换,程序实现,else,if,(x,%,3 = 1) ,handle(x,- 1) / 3);,cout, 1;,else,handle(x,+ 1) / 3);,cout, -;,数制转换,程序实现,else,if,(x 0) ,if,(-x,%,3 = 0) ,handle(x,/ 3);,cout, 0;,数制转换,程序实现,else,if,(-x % 3 = 1) ,handle(x,+ 1) / 3);,cout, -;,else,handle(x,- 1) / 3);,cout,src,) ,if,(,src,= 0),cout, 0;,else,handle(src,);,cout, 0) or (not Pizza and Hate 0),大众批萨,问题分析,筛法,Pizza,的口味总数为,2,16,=65536,；,建立口味列表，初始时所有口味都在列表中；,枚举每种需求，用需求去过滤口味列表中的口味,列表中剩下的口味就为问题的解,大众批萨,程序实现,const,int,maxPerson,= 16;,const,int,maxToppings,= 16;,short,wantmaxPerson,+ 1,hatemaxPerson,+ 1;,int,pizzaID,;,short mask,personCount, i;,string s;,大众批萨,程序实现,int,main() ,freopen(“PIZZA.IN,”, “r”,stdin,);,freopen(“PIZZA.OUT,”, “w”,stdout,);,/,建立批萨约束,personCount,= 0; /,初始化人数,cin, s; /,读入批萨约束的字符串,while,(s != “.”) ,大众批萨,程序实现,+,personCount,;,wantpersonCount, = 0;,hatepersonCount, = 0;,for,(i = 1; i = (,length(s,) - 1) / 2; +i) ,大众批萨,程序实现,mask = 1, s;,大众批萨,程序实现,/,枚举批萨并判断是否符合要求,pizzaID,= 0;,do,i = 1; /,判断每个口味约束,while,(i 0 | ,pizzaID,&,hatei, 0) ,+i; /,这个人将接受这个批萨,else,break;,大众批萨,程序实现,/,批萨符合所有的口味约束,if,(i ,personCount,) break;,+,pizzaID,;,while,(,pizzaID,!= (1 ,maxToppings,);,/,输出结果,/,没有符合要求的批萨,if,(,pizzaID,= (1 ,maxToppings,) ,cout, “No pizza can satisfy these requests.”,endl,;, else ,大众批萨,程序实现,cout, “Toppings: ”;,/,输出批萨的口味,for,(i = 0; i ,i) & 1) = 1) ,cout, (char) (i + 65);,cout,endl,;,return 0;,作业,1259,求连续素数和,1240,十进制少了,4,的计数,1231,求两个素数积,1214,数列找规律,1203,求一个数的立方的尾数是原数,1206,解方程,1099,线性方程,1020,1014,1119, 1382,1500,
展开阅读全文