算法设计ppt课件第四章数论.ppt

数论,目录,数论相关知识及其基本算法 自然数和整数 整除 最大公约数和最小公倍数 同余素数 数论解题样例,自然数和整数,自然数有一个起始的自然数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|(ab)如果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,代码,同余,同余设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)，则anbn(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 mi)，i=1,2,n，l=lcm(m1,m2,mn)，则ab(mod l)如果p为素数，则ap a(mod p)；如果gcd(a,p)=1，则ap-1 1(mod p),素数和合数,素数自然数中，除了1之外，只能被1和该数自身整除的数大于1的正整数，如果仅有的正因子是1和则称为素数（prime）。大于1又不是素数的正整数称为合数（compound）。如果n是合数，那么n必有一个小于或等于sqrt(n)的素因子。,素数和合数,其他-2是最小的素数2是唯一一个偶素数算术基本定理每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的“乘积”可以有0个、1个或多个素因子）。,筛法求素数,代码（筛法求素数）,代码（筛法求素数）,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的平方根中那些合数也是没有必要用来判断的。如果事先生成一个素数表，循环的次数还可以降低。利用素数表来求解。,代码（原始的素数判定方法）,代码（改进的素数判定方法1）,代码（改进的素数判定方法2）,解题样例,K尾相等数3n+1数链问题负权数质多项式猴子舞数制转换大众批萨,K尾相等数,对于一个自然数K（K1），若存在自然数M和N（MN），使得KM和KN均大于或等于1,000，且它们的末尾三位数相等，则称M和N是一对“K尾相等数”。求M+N值最小的K尾相等数。,K尾相等数问题分析,对于一个数，它的幂是无穷无尽的，但是我们可以注意到末尾三位数只有1,000个，也就是表明一定会有重复的末尾三位数，当一个数的末尾三位数一定时，它的下一次幂的末尾三位数也一定了。也就是说当第一次重复出现大于等于1,000的末尾三位数时，这就是我们要求的M和N。,K尾相等数要注意的问题,KM和KN要大于或等于1,00025:25 625 15625 390625对应的末位：25 625 625 625K要做预处理K mod 10001025：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所有的链长,3n+1数链问题程序实现,int a,b,maxlen;int linklen(int x)int l=1;while(x!=1)+l;if(x,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 maxlen;return 0;,负权数,对R进制数N，其绝对值可以用各位的数码乘以R的幂：N=anRn+an-1Rn-1+a0R0来表示。这里的R可以是正数也可以是负数。当R是负数时，我们称之为负权数。举例来说，10进制数-15用-2进制数来表示就是110001：-15=1(-2)5+1(-2)4+1(-2)0求10进制数的R进制的形式。,负权数问题分析,负权数问题分析,负权数问题分析,例：N=53,R=-253(10)=110101(2)53=1|-2|5+1|-2|4+1|-2|2+1|-2|01|-2|5=1(-2)6+1(-2)5 1|-2|4=1(-2)4，1|-2|2=1(-2)2，1|-2|0=1(-2)053=1(-2)6+1(-2)5+1(-2)4+1(-2)2+1(-2)053(10)=1110101(-2),负权数问题分析,负权数要注意的问题,进位问题 N=6,R=-26(10)=110(2)6=1|-2|2+1|-2|11|-2|1=1(-2)2+1(-2)11|-2|2=1(-2)2 6(10)=210(-2)?2(-2)2=1|-2|3=1(-2)4+1(-2)36(10)=11010(-2),负权数程序实现,int n,r,len;int a17;,负权数程序实现,/计算void comput()int i,p,n1,r1;n1=abs(n);r1=abs(r);len=-1;memset(a,0,sizeof(a);,负权数程序实现,/通过连除求余得到|N|的|R|进制形式 while(n1 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 endl;,负权数程序实现,void run()/若读到数据文件的结束符号，程序结束 while(cin n r)/无论在什么进制，0仍是0 if(n=0)cout 0 endl;else comput();print();,负权数程序实现,int main()freopen(“NEGATIVE.IN”,“r”,stdin);freopen(“NEGATIVE.OUT”,“w”,stdout);run();return 0;,质多项式,给定多项式f(x)=anxn+an-1xn-1+a0 x0，如果an0，称f(x)是一个n次多项式。给定多项式f(x)，如果找不到次数至少为1的多项式g(x)和h(x)满足f(x)=g(x)h(x)，称f(x)是质多项式。为了简化起见，规定多项式的各项的系数只能取0或1。并且重新定义在0,1上的加法和乘法：0+0=0,0+1=1,1+0=1,1+1=000=0,01=0,10=0,11=1问题：对给定的正整数k，求出次数为k的质多项式，满足ak2k+ak-12k-1+a020的值最小。,质多项式问题分析,用求素数的方法求解核心问题是如何实现多项式除法,质多项式问题分析,加法0+0=0,0+1=1,1+0=1,1+1=00 XOR 0=00 XOR 1=11 XOR 0=11 XOR 1=0其逆运算减法也是异或运算,质多项式问题分析,(X2+X)(X+1)=X3+X 1 1 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次多项式共有2n个；从素数得到的经验：n次质多项式不止一个第一个n次质多项式离xn不会太远,质多项式程序实现,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(wa-wb);,质多项式程序实现,while(a!=b,质多项式程序实现,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 endl;return;,质多项式程序实现,for(i=30;i=1;-i)if(bini=p)p-=bini;cout“x”i+;cout 1 endl;,质多项式程序实现,int main()freopen(“PRIME.IN”,“r”,stdin);freopen(“PRIME.OUT”,“w”,stdout);init();cin k;,质多项式程序实现,while(k!=0)now=bink-1;do now+=2;flag=true;for(i=2;i=bin(k+1)/2+1-1;+i)if(divide(now,i),质多项式程序实现,flag=false;break;while(!flag);print(now);cin k;return 0;,猴子舞(选讲),猴子舞是由N只猴子同时进行的。开始时，地上有N个圆圈，每个圆圈上站了一只猴子。地上还有N个箭头，每个圆圈恰好是一个箭头的起点和另一个箭头的终点，并且没有一个圆圈同时是某个箭头的起点和终点。表演开始时，所有的猴子同时按它所站的圆圈的箭头的方向跳到另一个圆圈中，这作为一步。当所有的猴子都回到自己原来所站的圆圈时，表演便结束了。求对于N可以达到的最大步数。,猴子舞问题分析,建模给定一个正整数N，要求若干个数A1,A2,Am(A1+A2+Am=N)，满足不存在 B1,B2,Bp(B1+B2+Bp=N)，使得lcm(B1,B2,Bp)lcm(A1,A2,Am),猴子舞问题分析,搜索法枚举所有可能的分解方式，求lcm(最小公倍数）搜索范围比较大lcm需要用到高精度乘法,猴子舞问题分析,搜索剪枝N=A1+A2+Am，如果Ai=Aj，显然其中一个对最小公倍数没有贡献，所以要求AiAj；优先考虑Ai是素数的情况，如果Ai是互不相同的素数，对lcm的贡献很大的；保证Ai之间是互质的，因为如果Ai、Aj不互质会浪费掉部分分解，当Ai之间互质时，计算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,猴子舞程序实现,/乘数在integer范围内的高精度乘法void longmul(TLongint,猴子舞程序实现,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=indexi-1;+j)longmul(res,listi);,猴子舞程序实现,/特殊处理2和3两个素数 if(index0=0)if(index1=0,猴子舞程序实现,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-1)findresult(num-val,k+1);val=val*listk;+indexk;if(val=num)checkresult(0,k);,猴子舞程序实现,/含有1元素的搜索void findresult1(int num,int k)int val;val=listk;indexk=0;,猴子舞程序实现,if(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 num-1)findresult1(num-val,k+1);val=val*listk;+indexk;if(val=num)checkresult(0,k);,猴子舞程序实现,void printresult()int i;for(i=max.len-1;i=0;-i)cout max.datai;cout endl;,猴子舞程序实现,void process(int num)memset(max,0,sizeof(max);memset(index,0,sizeof(index);findresult(num,1);,猴子舞程序实现,if(num=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，即132+031+130=10，这种数制的-0表示十进制数的-3，即-131+030=-3。要求把给定的有符号整数转换为新数制的数。,数制转换问题分析,证明存在性整数0的新数制表示是0；整数1的新数制表示是1；整数2的新数制表示是1-；整数-1的新数制表示是-；整数-2的新数制表示是-1；假设对一切k2，对|X|K的所有命题X成立，以下证K+1和-K-1的新数制表示是存在的K mod 3=0，则由归纳假设K/3存在新数制表示A1A2An，则K+1存在新数制表示A1A2An1K mod 3=1，则由归纳假设(K+2)/3存在新数制表示A1A2An，则K+1存在新数制表示A1A2An-K mod 3=2，则由归纳假设(K+1)/3存在新数制表示A1A2An，则K+1存在新数制表示A1A2An0同理-K-1也存在新数制表示,数制转换问题分析,证明唯一性设有新数制的两种表示A1A2An和B1B2Bn，不足n位的在前面用零补足。由新数制的定义可知：3n-1A1+3n-2A2+3An-1+An=3n-1B1+3n-2B2+3Bn-1+Bn上式两边对3取模可得An=Bn，于是有：3n-2A1+3n-3A2+An-1=3n-2B1+3n-3B2+Bn-1上式两边对3取模可得An-1=Bn-1使用上述方法，通过有限步即得Ai=Bi,数制转换问题分析,从个位开始到最高位逐位确定结果输入X；若为0则输出0并结束，否则下一步；置结果符号串S为空；若为0则输出S并结束，否则下一步；若X0转(9)，否则下一步；若X mod 3=0，X=X/3，S=0+S，转(5)；若X mod 3=1，X=(X-1)/3，S=1+S，转(5)；若X mod 3=2，X=(X+1)/3，S=-+S，转(5)；若-X mod 3=0，X=X/3，S=0+S，转(5)；若-X mod 3=1，X=(X+1)/3，S=-+S，转(5)；若-X mod 3=2，X=(X-1)/3，S=1+S，转(5)；,数制转换问题分析,-011-10111-1-01-110-10010111-,数制转换程序实现,int src;void handle(int x)if(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 1;,数制转换程序实现,int main()freopen(“RADIX.IN”,“r”,stdin);freopen(“RADIX.OUT”,“w”,stdout);while(cin src)if(src=0)cout 0;else handle(src);cout endl;return 0;,大众批萨,Pizza有A,B,P16种口味。可以用一行符号来描述某人接受的pizza。+O-H+P：表示某位朋友接受一个包含O口味，或不含H口味，或包含P口味的批萨；-E-I-D+A+J：表示某位朋友接受一个不含E口味或I口味或D口味的，或带有A口味或J口味的批萨。给出一系列要求，求一种满足条件的Pizza。,大众批萨问题分析,将每种批萨口味看成是一个布尔变量，用变量A的取值（True或False）表示批萨是否有A口味；将一个批萨看成是变量A,B,P的一组赋值，那么批萨ACFO就是A、C、F和O四个变量取值True，而其他变量取值False的一组赋值；将每条口味约束看成是变量A,B,P及其否定的析取式，例如，口味约束+O-H+P可以表示为OHP；,大众批萨问题分析,将每个批萨约束看成是所有口味约束的合取式，考虑以下约束：+A+B-C-D+A-B+C+D等价于合取式：(AB)(CD)(AB)(CD),大众批萨问题分析,生成法将上合取式展开得ACDACDABCDABCDABCDABCD每个析取元为True都可以满足要求，比如第一个析取元为ACD，即一个包含AC口味且不含D口味的Pizza都是问题的解，包不包含B,E,F,等口味对问题的解没有影响。,大众批萨问题分析,枚举法枚举批萨所有可能的口味组合；对每种口味组合，扫描批萨约束，判断是否符合要求。用16位二进制数表示Pizza两个16位二进制数表示口味需求+A-B-D+E表示为：Want:100010000Hate:010100000判断某个Pizza是否符合口味需求：(Pizza and Want 0)or(not Pizza and Hate 0),大众批萨问题分析,筛法Pizza的口味总数为216=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,大众批萨程序实现,/批萨符合所有的口味约束 if(i personCount)break;+pizzaID;while(pizzaID!=(1 maxToppings);/输出结果/没有符合要求的批萨 if(pizzaID=(1 maxToppings)cout“No pizza can satisfy these requests.”endl;else,大众批萨程序实现,cout i),作业,1259 求连续素数和1240 十进制少了4的计数1231求两个素数积1214 数列找规律1203求一个数的立方的尾数是原数1206 解方程1099 线性方程1020,1014,1119,1382,1500,