算法设计课件-第四章数论C++14.ppt

1、数论目录目录l数论相关知识及其基本算法数论相关知识及其基本算法 自然数和整数自然数和整数 整除整除 最大公约数和最小公倍数最大公约数和最小公倍数 同余同余素数素数 l数论解题样例数论解题样例 自然数和整数自然数和整数l自然数自然数有一个起始的自然数有一个起始的自然数0；任何一个自然数都有后继；任何一个自然数都有后继；0不是任何自然数的后继；不是任何自然数的后继；不同的自然数有不同的后继；不同的自然数有不同的后继；存在一组与自然数有关的命题。假设此命题对起始的自然数存在一组与自然数有关的命题。假设此命题对起始的自然数0成立，如果该命题对任一自然数成立可以推导出对其后继成立，如果该命题对任一自然数

2、成立可以推导出对其后继也成立，则此命题对所有自然数都成立。也成立，则此命题对所有自然数都成立。l整数整数 负整数与自然数一起构成整数负整数与自然数一起构成整数 整除整除 l一个整数一个整数a能被另一个整数能被另一个整数d整除，记做整除，记做d|a，意味意味着存在某个整数着存在某个整数k，有，有a=kd。l如果如果a 0且且 d|a，则，则IdI 0,则称称d是是a的约数（的约数（Divisor）；）；l一个整数一个整数a的约数最小为的约数最小为1，最大为，最大为IaI，每个整数每个整数a都可被其平凡约数都可被其平凡约数1和和a整除；整除；a的非平凡约数也称的非平凡约数也称为为a的因子（的因子（

3、Factor）；）；l例：例：30的约数为的约数为1，3，5，6，10，15，30，其中，其中3，5，6，10，15为为30的因子的因子整除整除l整除的性质整除的性质 如果如果d|a，则对于任意整数，则对于任意整数k有有d|ka如果如果d|a且且d|b，则，则d|(ab)如果如果b|a 且且a|b，则，则a=b如果如果a|b且且b|c，则，则a|c整除关系具有传递性，由于它显然也具有自反性和反整除关系具有传递性，由于它显然也具有自反性和反对称性，所以它是一个偏序关系。对称性，所以它是一个偏序关系。整除整除l几种特殊的整除的例子几种特殊的整除的例子若若2能整除能整除a的最末位，则的最末位，则2|

4、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最大公约数最大公约数l公约数公约数如果如果d是是a的约数

5、并且也是的约数并且也是b的约数，则的约数，则d是是a与与b的的公约数公约数(Common Divisor)1是任意两个整数的公约数是任意两个整数的公约数l最大公约数（最大公约数（Greatest Common Divisor）所有公约数中最大的一个，记做所有公约数中最大的一个，记做gcd(a,b)最大公约数最大公约数l最大公约数的性质：最大公约数的性质：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

6、和和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);最小公倍数最小公倍数l公倍数如果m是a的倍数并且也是b的倍数，则m是a与b的公倍数 l最小公倍数所有公倍数中最小的那个，记

7、做lcm(a,b)l最小公倍数的性质lcm(a,b)=a*b/gcd(a,b)辗转相除法求最大公约数辗转相除法求最大公约数l原理如果q和r是a除以b的商和余数，即a=bq+r，则gcd(a,b)=gcd(b,r)l举例gcd(1001,767)=gcd(767,234)=gcd(234,65)=gcd(65,39)=gcd(39,26)=gcd(26,13)=gcd(13,0)=13代码代码辗转相除法求最大公约数辗转相除法求最大公约数/要求a,b不同时为0int gcd(int a,int b)if(b=0)return a;return gcd(b,a%b);利用最大公约数求最小公倍数利用最

8、大公约数求最小公倍数int lcm(int a,int b)if(a*b=0)return 0;return a*b/gcd(a,b);同余同余l同余设m是正整数，a,b是整数，如果m|(a-b)，则称a和b关于模m同余，记作ab(mod m)或者说，如果a,b除以m的余数相等，则称a和b关于模m同余l同余的性质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)同余同余l同余的性质(cont.)如果ab(mod m)，则anbn

9、(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)素数和合数素数和合数l素数素数自然数中，除了自然数中，除了1之外，只能被之外，只能被1和该数自身整除的和该数自身整除的数数l大于大于1的正整数的正整数，如果仅有的正因子是，如果仅有的正因子是1和和则称则称为为素数（素数（prim

10、e）。大于）。大于1又不是素数的正整数称为合数又不是素数的正整数称为合数（compound）。如果）。如果n n是合数，那么是合数，那么n n必有一个小于必有一个小于或等于或等于sqrt(n)的素因子。的素因子。素数和合数素数和合数l其他其他 -2是最小的素数是最小的素数2是唯一一个偶素数是唯一一个偶素数l算术基本定理算术基本定理每个正整数都可以惟一地表示成素数的乘积，其中每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的素数因子从小到大依次出现（这里的“乘积乘积”可以可以有有0个、个、1个或多个素因子）。个或多个素因子）。筛法求素数筛法求素数234567891011

11、121314151617181920212223242526234567891011121314151617181920212223242526234567891011121314151617181920212223242526234567891011121314151617181920212223242526234567891011121314151617181920212223242526代码（筛法求素数）代码（筛法求素数）const int MAX=10000;bool primeMAX+1;void searchprime()memset(prime,true,sizeof(prime

12、);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;素数的判定素数的判定l原始的判定方法，根据素数的定义原始的判定方法，根据素数的定义l改进的判定方法改进的判定方法1，x可以分解为两个整数可以分解为两个整数a,b的积，即的积，即 x=a*b，ab，那么，那么a sqrt(x)l改进的判定方法改进的判定方法2，其实，其实2到到x的平方根中那些的平方根中那些合数也是没有必要用来判断的。如果事先生成合数也是没有必

13、要用来判断的。如果事先生成一个素数表，循环的次数还可以降低。利用素一个素数表，循环的次数还可以降低。利用素数表来求解。数表来求解。代码（原始的素数判定方法）代码（原始的素数判定方法）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;代码（改进的素数判定方法代码（改进的素数判定

14、方法2）bool isPrime(int x)int i=0;/list是预先生成好的素数表 while(listi*listi 1），若存在自然数M和N（MN），使得KM和KN均大于或等于1,000，且它们的末尾三位数相等，则称M和N是一对“K尾相等数”。l求M+N值最小的K尾相等数。K尾相等数问题分析 对于一个数，它的幂是无穷无尽的，但是我们可以注意到末尾三位数只有1,000个，也就是表明一定会有重复的末尾三位数，当一个数的末尾三位数一定时，它的下一次幂的末尾三位数也一定了。也就是说当第一次重复出现大于等于1,000的末尾三位数时，这就是我们要求的M和N。K尾相等数要注意的问题lKM和KN

15、要大于或等于1,00025:25 625 15625 390625对应的末位：25 625 625 625lK要做预处理K mod 10001025：1025 1050625 1103812890625 1159693418212890625对应的末位：25 625 625 625K尾相等数程序实现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

16、=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数链问题 有这样一个问题，如下：有这样一个问题，如下：1.输入一个正整数输入一个正整数n；2.如果如果n=1则结束；则结束；3.如果如果n是奇数则是奇数则n变为变为3*n+1，否则，否则n变为变为n/2；4.转入第转入第2步。步。例如对于输入的正整数例如对于输入的正整数22，则数列为：，则数列为：22 11 34 17 52 26 13 40 20 10 5 1

17、6 8 4 2 1对于任意一个正整数，经过以上算法最终会推到对于任意一个正整数，经过以上算法最终会推到1。对于给定的正。对于给定的正整数整数n，我们把显示出来的数的个数定义为，我们把显示出来的数的个数定义为n的链长，例如的链长，例如22的的链长为链长为16。对于任意一对正整数对于任意一对正整数i和和j，求，求i、j之间的最长链长。之间的最长链长。3n+1数链问题问题分析 l这是一道很简单的题目，无大多其他的技巧，这是一道很简单的题目，无大多其他的技巧，只需要按照题目的要求一步步做下去即可。对只需要按照题目的要求一步步做下去即可。对于每一个正整数，可以很容易求得它的数链长于每一个正整数，可以很容

18、易求得它的数链长度。度。3n+1数链问题要注意的问题li、j之间包括i和j题目的例子i=1,j=10l进一步的优化记录下1至10000所有的链长123456789101283691742073n+1数链问题程序实现int a,b,maxlen;int linklen(int x)int l=1;while(x!=1)+l;if(x&1)x=x*3+1;/如果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 m

19、ain()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-a

20、p;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质多项式问题分析l(X3+X)/(X+1)=X2+X 1 1 0 -1 1/1 0 1 0XOR 1 1 -1 1 0XOR 1 1 0 -0质多项式问题分析l(X7+X5+X3+X2+X+1)/(X4+X3+X+1)1 1 0 1 -1 1 0 1 1/

21、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质多项式需要注意的问题l除了次数为1的情况，质多项式都包含常数项1；l系数只能为0和1的n次多项式共有2n个；l从素数得到的经验：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 di

22、vide(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=tru

23、e;for(i=2;i k;return 0;猴子舞(选讲)l猴子舞是由N只猴子同时进行的。开始时，地上有N个圆圈，每个圆圈上站了一只猴子。地上还有N个箭头，每个圆圈恰好是一个箭头的起点和另一个箭头的终点，并且没有一个圆圈同时是某个箭头的起点和终点。表演开始时，所有的猴子同时按它所站的圆圈的箭头的方向跳到另一个圆圈中，这作为一步。当所有的猴子都回到自己原来所站的圆圈时，表演便结束了。l求对于N可以达到的最大步数。猴子舞问题分析l建模给定一个正整数N，要求若干个数A1,A2,Am(A1+A2+Am=N)，满足不存在 B1,B2,Bp(B1+B2+Bp=N)，使得lcm(B1,B2,Bp)lcm(

24、A1,A2,Am)jiAA jiAA jiAA jiAA 猴子舞问题分析l搜索法枚举所有可能的分解方式，求lcm(最小公倍数）搜索范围比较大lcm需要用到高精度乘法猴子舞问题分析l搜索剪枝N=A1+A2+Am，如果Ai=Aj，显然其中一个对最小公倍数没有贡献，所以要求AiAj；优先考虑Ai是素数的情况，如果Ai是互不相同的素数，对lcm的贡献很大的；保证Ai之间是互质的，因为如果Ai、Aj不互质会浪费掉部分分解，当Ai之间互质时，计算lcm时把Ai相乘即可；猴子舞需要注意的问题l不能有长度为1的圈猴子舞程序实现const int MAXN=300;typedef int TArray100;s

25、truct 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范围内的高精度

26、乘法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

27、-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

28、(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

29、 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

30、”,“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。要求把给定的有符号整数转换为新数制的数。数制转换问题分析l证明存在性整数0的新数制表示是0；整数1的新数制表示是1；整数2的新数制表示是1-；整数-1的新数制表示

31、是-；整数-2的新数制表示是-1；假设对一切k2，对|X|K的所有命题X成立，以下证K+1和-K-1的新数制表示是存在的lK mod 3=0，则由归纳假设K/3存在新数制表示A1A2An，则K+1存在新数制表示A1A2An1lK mod 3=1，则由归纳假设(K+2)/3存在新数制表示A1A2An，则K+1存在新数制表示A1A2An-lK mod 3=2，则由归纳假设(K+1)/3存在新数制表示A1A2An，则K+1存在新数制表示A1A2An0同理-K-1也存在新数制表示数制转换问题分析l证明唯一性设有新数制的两种表示A1A2An和B1B2Bn，不足n位的在前面用零补足。由新数制的定义可知：3

32、n-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数制转换问题分析l从个位开始到最高位逐位确定结果1.输入X；2.若为0则输出0并结束，否则下一步；3.置结果符号串S为空；4.若为0则输出S并结束，否则下一步；5.若X 0)if(x%3=0)handle(x/3);cout 0;数制转换程序实现 else if(x%3=1)handle(x-1)/3);cout 1;e

33、lse 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)大众批萨问题分析l筛法筛法Pizza的口味总数为的口味总数为216=65536；建立口味列表，初始时所有口味都在列表中；建立口味列表，初始时所有口味都在列表中；枚举每种需

34、求，用需求去过滤口味列表中的口味枚举每种需求，用需求去过滤口味列表中的口味列表中剩下的口味就为问题的解列表中剩下的口味就为问题的解大众批萨程序实现程序实现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);/建立批萨约束

35、 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;大众批萨程序实现程序实现 /批萨符合所有的口味约束 i

36、f(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;作业作业l1259 求连续素数和求连续素数和l1240 十进制少了十进制少了4的计数的计数l1231求两个素数积求两个素数积l1214 数列找规律数列找规律l1203求一个数的立方的尾数是原数求一个数的立方的尾数是原数l1206 解方程解方程l1099 线性方程线性方程l1020,1014,1119,1382,1500