1、第第3次课次课 数论中的程序设计数论中的程序设计沈云付沈云付上海大学计算机工程与科学学院上海大学计算机工程与科学学院 本章主要内容本章主要内容1 1、最大公因数与最小公倍数、最大公因数与最小公倍数2 2、求整系数一次不定方程、求整系数一次不定方程ax+by=cax+by=c的解的解3 3、求解模线性方程、求解模线性方程4 4、求模、求模m m的逆元素算法的逆元素算法5 5、模线性方程组与中国剩余定理、模线性方程组与中国剩余定理6 6、模取幂运算与素数测试、模取幂运算与素数测试7 7、实例研究、实例研究1234567891、最大公因数与最小公倍数、最大公因数与最小公倍数公约数和最大公约数的概念公
2、约数和最大公约数的概念最大公约数的一种求法最大公约数的一种求法分解因子分解因子最大公约数性质与欧几里德转辗相除法最大公约数性质与欧几里德转辗相除法欧几里德转辗相除法欧几里德转辗相除法欧几里德算法实现欧几里德算法实现实例实例 求最大公因数求最大公因数问题描述：问题描述：从输入文件中读取一组数据，求最大公因数。从输入文件中读取一组数据，求最大公因数。输入：输入：输输入入有有若若干干行行。每每一一行行上上有有两两个个整整数数x x，y y，是是一一组组测测试试数数据，他们之间用一个空格隔开。据，他们之间用一个空格隔开。输出：输出：对对每每一一组组测测试试数数据据，每每行行输输出出这这两两个个整整数数
3、的的最最大大公公因因数数。如无最大公因数，则标明如无最大公因数，则标明“no GCDno GCD”。输出样例：输出样例：(6,11)=1(0,0)noGCD(5,0)=5输入样例：61100501）公因数和最大公因数的概念）公因数和最大公因数的概念公公因因数数：如如果果d是是a的的因因数数并并且且也也是是b的的因因数数，则则d是是a与与b的的公因数公因数例：例：30的正因数：的正因数：1，2，3，5，6，10，15、30；24的正因数：的正因数：1，2，3，4，6，12，24；24与与30的正公因数有：的正公因数有：1、2、3、6。1是任意两个整数的公因数；是任意两个整数的公因数；最大公因数：
4、两个不同时为最大公因数：两个不同时为0的整数的整数a与与b的最大公因数是其的最大公因数是其值为最大的公因数，记作值为最大的公因数，记作gcd(a,b)。gcd(24,30)6。最大公约数的一种求法最大公约数的一种求法分解因子分解因子 因因为为gcd(agcd(a，b)b)gcd(|a|gcd(|a|，|b|)|b|)，所所以以可可考考虑虑非非负负整整数的情况。数的情况。通过求因数，可求通过求因数，可求a a和和b b的素数因子分解：的素数因子分解：a=a=，b=b=于是整数于是整数a a和和b b的最大公因数为：的最大公因数为：gcd(agcd(a，b)b)注意：求一个数的素因子分解问题是注意
5、：求一个数的素因子分解问题是NP问题。目前问题。目前用穷举方法可求不太大的整数的整数分解，这种方用穷举方法可求不太大的整数的整数分解，这种方法不是有效的。只能用优化方法改善计算效率。法不是有效的。只能用优化方法改善计算效率。最大公因数性质最大公因数性质性质：性质：（1）gcd(a，b)gcd(a，b)（2）gcd(a，b)gcd(a+kb，b)，k为任何整数为任何整数（3）gcd(a，b)gcd(b，a mod b)（4）如）如a是非零整数，那么是非零整数，那么gcd(a，0)|a|欧几里德转辗相除法的依据：欧几里德转辗相除法的依据：gcd(agcd(a，b)b)gcd(bgcd(b，a mo
6、d b)a mod b)可可求整数求整数a a和和b b的最大公因数的最大公因数 2）最小公倍数）最小公倍数公倍数：如果公倍数：如果m是是a的倍数并且也是的倍数并且也是b的倍数，那么称的倍数，那么称m是是a与与b的公倍数。的公倍数。最小公倍数：两个非零整数最小公倍数：两个非零整数a与与b的最小公倍数是的最小公倍数是a与与b的公的公倍数中数值最小正的数。倍数中数值最小正的数。记作记作lcm(a，b)（或简写为（或简写为a，b）。）。lcm(a，b)lcm(|a|，|b|)通过通过a和和b的标准分解，可以求出整数的标准分解，可以求出整数a和和b的最小公倍数：的最小公倍数：lcm(a，b)=最小公倍
7、数与最大公因数关系最小公倍数与最大公因数关系 3）欧儿里德算法）欧儿里德算法给定任意两个正整数给定任意两个正整数a a和和b b gcd(gcd(a，b)=)=结论：求最大公因数的递归程序求最大公因数的递归程序用欧几里德转辗相除法构造一个求最大公因数的递归程序。用欧几里德转辗相除法构造一个求最大公因数的递归程序。输入：输入：非负整数非负整数a a、b b返回：返回：a a和和b b的最大公因数的最大公因数long gcd(long a,long b)long gcd(long a,long b)long m;long m;if(b=0)&(a=0)/if(b=0)&(a=0)/表示无最大公因数
8、表示无最大公因数 return-1;return-1;if(b=0)return a;if(b=0)return a;else m=gcd(b,else m=gcd(b,a%ba%b););return m;return m;求最大公因数的无递归程序求最大公因数的无递归程序int gcd(int a,int b)int c;if(a=0)return b;while(b!=0)c=b,b=a%b,a=c;return a;2、利用欧几里德算法求整系数一次、利用欧几里德算法求整系数一次不定方程不定方程ax+by=c的解的解算法思想：算法思想：1.利用求利用求a,b的最大公因数的转辗相除过程，进行
9、多次逆推，的最大公因数的转辗相除过程，进行多次逆推，使最大公因数的表示式最终表示为使最大公因数的表示式最终表示为a与与b的线性组合的线性组合ax+by (x与与y可能为可能为0或负数或负数)。2.此时，此时，dgcd(a,b)3.做法：将欧几里德算法进行推广，使得该算法不仅能得做法：将欧几里德算法进行推广，使得该算法不仅能得出任意两个正整数出任意两个正整数a和和b的最大公因数的最大公因数d，而且还能计算出，而且还能计算出满足下式的整数满足下式的整数x和和y：d=ax+by反向递推反向递推辗转相除过程的逆推辗转相除过程的逆推记记类似地，记类似地，记一般地，一般地，于是有整数于是有整数x x和和y
10、 y满足：满足：d dgcd(agcd(a，b)b)ax+by ax+by 扩展欧几里德算法扩展欧几里德算法-递归实现递归实现输入整数输入整数a、b，返回，返回gcd(a，b)和对应等式和对应等式ax+by=d中的中的x,y。long extend_gcd(long a,long b,long&x,long&y)long t,m;if(b=0)&(a=0)return-1;/表示无最大公因数表示无最大公因数 if(b=0)x=1;y=0;return a;else m=extend_gcd(b,a%b,x,y);t=x;x=y;y=t-(a/b)*y;return m;扩展欧几里德算法扩展欧几
11、里德算法-无递归实现无递归实现int extend_gcd(int a,int b,int*x,int*y)int x0,x1,x2,y0,y1,y2;int r0,r1,r2,q;if(a=0)&(b=0)*x=0;*y=0;return-1;/gcd(a,b)不存在不存在if(a=0)&(b!=0)/a=0时不存在时不存在a的乘法逆元的乘法逆元*x=0;*y=1;return b;if(b=0)&(a!=0)/b=0时不存在时不存在b的乘法逆元的乘法逆元*x=1;*y=0;return a;if(a!=0)&(b!=0)x0=0;x1=1;r0=a;y0=1;r1=b;r2=r0%r1;y
12、1=0-r0/r1;x2=1;y2=y1;扩展欧几里德算法扩展欧几里德算法-无递归实现无递归实现(续续)while(r1%r2)!=0)r0=r1;r1=r2;q=r0/r1;x2=x0-x1*q;y2=y0-y1*q;x0=x1;x1=x2;y0=y1;y1=y2;r2=r0%r1;*x=x2;*y=y2;returnr2;mx+ny=c的整数解算法的整数解算法 设设d=gcd(m,n)，记，记m=ad，n=bd1.求特解：求整系数方程求特解：求整系数方程mx+ny=d的一个整数解的一个整数解x0，y0，2.求一般解：求一般解：若若 d不是不是c的因数，则整系数方程的因数，则整系数方程mx+
13、ny=c无无整数解；整数解；若若 d是是c的因数，记的因数，记c=gd，则整系数方程则整系数方程mx+ny=c一般解为一般解为：x=gx0+bt,y=gy0-at,t为任何整数为任何整数举例举例求下列整系数方程的整数解：求下列整系数方程的整数解：答案：略答案：略3、求解模线性方程、求解模线性方程1）模和同余模和同余模和同余：模和同余：设设a a、b b和和m m均为整数，且均为整数，且m0m0。如果。如果a a和和b b被被m m除所得的余数相同，那么称除所得的余数相同，那么称a a和和b b关于关于模模m m是是同余的，记同余的，记作作 几个等价定义：几个等价定义：b-ab-a能被能被m m
14、整除，记整除，记m|a-bm|a-b a a和和b b关于关于模模m m是是同余的同余的2）同余性质）同余性质4、设、设 ，那么那么1、2、3、(1)(2)(3)5、费马小定理：设、费马小定理：设a，p为正整数，且为正整数，且p为素数，为素数，(p,a)=1，那么那么剩余类与简化剩余系剩余类与简化剩余系1.剩余类：对于整数剩余类：对于整数a及模及模m，则集合，则集合A=x|xa(mod m)称为模称为模m关于关于a的一个剩余类。的一个剩余类。2.完全剩余系：完全剩余系：0，1，2，m-1是一个特殊的集合，元是一个特殊的集合，元素个数素个数m，其中任何两个数都不同余，称为完全剩余系。，其中任何两
15、个数都不同余，称为完全剩余系。3.任何任何m个元素的集合个元素的集合X，如果其中任何两个数都不同余，如果其中任何两个数都不同余，那么那么X也是一个完全剩余系。也是一个完全剩余系。4.既约剩余系：设既约剩余系：设m为正整数，在与为正整数，在与m既约的所有剩余类中，既约的所有剩余类中，每一个类中取一个数，构成一个集合每一个类中取一个数，构成一个集合X，则，则X称为模称为模m的的一个简化剩余系。一个简化剩余系。举例举例例例1：若：若p是素数，则是素数，则1，2，3，p-1是模是模p的一个既约剩的一个既约剩余系。余系。例例2：1，5，7，11是模是模12的一个既约剩余系。的一个既约剩余系。问题：与正整
16、数问题：与正整数m既约且小于等于既约且小于等于m的自然数全体之积的自然数全体之积Y被被m除后余数是几？除后余数是几？举例：举例：m=7，Y=1*2*3*4*5*6(mod 7)-1(mod 7)，正余数，正余数为6；m=13，Y=1*2*3*4*5*12(mod 13)(-1)(13-1)/2(mod 13)，正，正余数余数为1；m=21，Y=1*2*4*5*8*10*11*13*16*17*19*20Y(mod 21)1 (mod 21)2）模线性方程）模线性方程 相当于求相当于求根据前面求根据前面求 的步骤：的步骤：（1 1）求）求 ，使，使否则，否则，有有d d个解个解（4 4）的所有解
17、可写为：的所有解可写为：（3 3）由）由 ，改写得：，改写得：于是于是 的一个解为：的一个解为：（2 2）若）若d bd b，则，则无解；无解；方程与同余式求解举例方程与同余式求解举例（2 2）求）求（3 3）求）求例：（例：（1 1）求）求4、求、求mod m的逆元素算法的逆元素算法对整数对整数a，满足，满足ax 1(mod m)的解的解x称为称为a关于模关于模m的逆的逆元素元素。是前面模线性方程的特例。是前面模线性方程的特例。结论：对整数结论：对整数a，m（m0）,ax 1(mod m)有解，当且有解，当且仅当，仅当，gcd(a，m)=1也可用直接用扩展欧几里得算法进行求解。也可用直接用扩
18、展欧几里得算法进行求解。求求 的算法的算法 举例求解：求解：（1 1）（2 2）（3 3）（4 4）求求mod m的逆元素的无递归程序：的逆元素的无递归程序：long mod_reverse(long a,long m)long y=0,x=1,r=a%m,q,t,mm=m;/初始化初始化if(r0)r=r+m;while(m%r)!=0)a=m;m=r;q=a/m;r=a%m;t=x;x=y-x*q;y=t;if(r!=1)return 0;if(x0)x=x+mm;return x;5、模线性方程组与中国剩余定理、模线性方程组与中国剩余定理“韩信点兵韩信点兵”问题问题：有兵一列，三三数之余
19、二，五五数之余三，七七数之有兵一列，三三数之余二，五五数之余三，七七数之余二，问兵几何？余二，问兵几何？可写成数学表示形式，求可写成数学表示形式，求x求解模线性方程组求解模线性方程组 中国剩余定理中国剩余定理求解步骤求解步骤 例：解同余方程组例：解同余方程组 中国剩余定理中国剩余定理程序实现程序实现long ChinaRemainder(int m0,int b)long d,x,y,n,m=1,a=0;int i;for(i=1;i=n;i+)m=m*m0i;for(i=1;i=n;i+)MM=m/m0i;extend_gcd(MM,m0i,&x,&y);/或或x=mod_reverse(M
20、M,m0i);a=(a+MM*x*bi)%m;return a;6、模幂运算与素数测试、模幂运算与素数测试模幂运算就是在一个模下模幂运算就是在一个模下计算一个幂的值，即计算计算一个幂的值，即计算 (a，r和和m是正整数是正整数)素数测试就是指，在尽可能短的时间内，尽可能精确素数测试就是指，在尽可能短的时间内，尽可能精确地判断一个整数是否是素数。通过地判断一个整数是否是素数。通过费马小定理来判定小定理来判定一个一个整数的素性整数的素性，因此求模幂是重要任务。，因此求模幂是重要任务。1）模幂运算）模幂运算（1）模幂运算）模幂运算1累次计算法累次计算法：d d a ar r mod m mod m
21、(a mod m)*a)mod m)*a)mod m(a mod m)*a)mod m)*a)mod m*a)mod m *a)mod m 算法算法long modular_power1(long a,long r,long m)long d=1,k;a=a%m;for(k=0；k0)if(r%2)=1)d=(d*t)%m；r=r/2;t=t*t%m;return d;练习练习计算计算2）素数测试）素数测试费马小定理：设费马小定理：设a，p为正整数，且为正整数，且p为素数，为素数，(p,a)=1，那么那么有例外，如有例外，如2340 1（mod 341），但），但341是合数。是合数。素数测试
22、：设素数测试：设a a、n n为正整数为正整数（1 1）若）若 ，则，则n n一定为合数一定为合数（2 2）若）若 ，则几乎可以肯定地确认，则几乎可以肯定地确认n n为素为素数，因出错概率很小数，因出错概率很小 Miller-Rabin素数测试算法框架素数测试算法框架输入：输入：n与与a（a在在2，n-1这些数中随机取值）这些数中随机取值）输出：出：true或或false S1.设设(bk,bk-1,b1,b0)为为n-1的二进制表示的二进制表示S2.d=1S3.For i=k downto 0 do x=d d=(d*d)mod n if(d=1)and(x 1)and(x n-1)then
23、 return true if(bi=1)then d=(d*a)(mod n)End ForS4.if(d 1)then return true S5.return false 3）欧拉定理）欧拉定理设设a和和m 是整数，（是整数，（m00）。记）。记(m)是是1 1到到m的整数中的整数中与与m m互素的整数的个数，则互素的整数的个数，则a(m)1(mod 1(mod m)。费马小定理是欧拉定理的特例费马小定理是欧拉定理的特例 4）公钥密码与）公钥密码与RSA公开密钥算法是在公开密钥算法是在1976年由美国斯坦福大学的迪菲年由美国斯坦福大学的迪菲（Diffie）和赫尔曼）和赫尔曼(Hellm
24、an)提出提出目前最流行的目前最流行的RSA是是1977年由年由MIT教授教授Rivest,Shamir和和Adleman三人共同开发。三人共同开发。密密钥的的产生生选择两个大素数，选择两个大素数，p 和和q，计算出，计算出n=qp，n称为称为RSA算法算法的模数。的模数。n公开，公开，p、q 必须保密。必须保密。n的长度大于的长度大于1024位位计算计算n的欧拉数的欧拉数 (n)=(p-1)(q-1)。随机选择加密密钥随机选择加密密钥e，从，从0,(n)-1中选择一个与中选择一个与(n)互质互质的数的数e，e公开公开计算解密密钥计算解密密钥d,满足满足de1(mod (n)。其中。其中n和和
25、d也要互质。也要互质。数数e和和n做公钥，做公钥，d做私钥。做私钥。两个素数两个素数p和和q不再需要，应该丢弃，不让任何人知道。不再需要，应该丢弃，不让任何人知道。加密与解密加密与解密1.加密信息 m（二进制表示）：首先把m分成等长数据块 m1,m2,.,mi，块长s，其中 2s n;do n/=5;count+=n;while(n);coutcount1，那么不能表示成，那么不能表示成Ax+By 形式的邮资的个形式的邮资的个数有无穷多，如以下数都不是数有无穷多，如以下数都不是Ax+By 形式：形式：1、1+A B、1+2 A B、1+n A B、如如d=gcd(A,B)=1，结果如何？，结果
26、如何？3)在在0到到AB-1内有内有 个整数个整数m可以写成可以写成 m=As+Bt 的形式，的形式，s，t是非负整数是非负整数。分析分析以下设以下设d=gcd(d=gcd(A,B)=1。结论：值至少为结论：值至少为AB的邮资都是可以用这两种邮票支付的。的邮资都是可以用这两种邮票支付的。不能支付的不超过不能支付的不超过AB-1-1个，而且可以用一个公式表示。个，而且可以用一个公式表示。需证明以下几点：需证明以下几点：1)不妨不妨设AB。对整数整数n，0nB，有整数，有整数x、y，使，使n=Ax+By，且且满足足0=AB时，任何时，任何m均可表示成均可表示成Ax+By的形式，的形式，x=0=0，
27、y=0=0。不能表示成不能表示成Ax+By形式的数的个数为形式的数的个数为 参考程序：易，略参考程序：易，略4 Josephus问题问题 问题描述：问题描述：JosephusJosephus问题：一一群群小小孩孩围成成一一圈圈，任任意意给定定一一个个数数m m，从从第第一一个个小小孩孩开开始始，顺时针方方向向数数，每每数数到到第第m m个个小小孩孩时，该小小孩孩便便离离开开。小小孩孩不不断断离离开开，圈圈子子不不断断缩小小。最最后后剩剩下的一个小孩是下的一个小孩是胜利者。究竟利者。究竟胜利者是第几个小孩呢？利者是第几个小孩呢？输入：输入：有有若若干干组组测测试试数数据据。每每一一行行有有一一个
28、个整整数数numnum，m m，分分别别代代表小孩个数和每隔多少小孩数数。表小孩个数和每隔多少小孩数数。numnum，m m1000010000。输出：输出：对每一每一组测试数据，数据，单行行输出出获胜的小孩的的小孩的编号。号。输入与输出样例输入与输出样例输入样例：输入样例：10 810 810 210 2输出样例：输出样例：1 15 5分析分析方法一：模拟法方法一：模拟法实际模拟数小孩出列的过程。用一个数组表示小孩围成实际模拟数小孩出列的过程。用一个数组表示小孩围成圈。对每个小孩赋以一个序号值作为小孩的标志。圈。对每个小孩赋以一个序号值作为小孩的标志。采用采用 “加加1 1求模求模”，当数到
29、数组尾的时候，下一个数组，当数到数组尾的时候，下一个数组下标值可以算得为下标值可以算得为0 0，从而回到数组首以继续整个过程。，从而回到数组首以继续整个过程。设：设：Max=10000;Max=10000;小孩最大个数小孩最大个数 numnum为小孩个数，为小孩个数，aMax;aMax;小孩数组小孩数组 每每次次数数m m个个小小孩孩，便便让让该该小小孩孩离离开开；下下标标加加1 1求求模模，使使下下标到达尾部后能返回到数组头。标到达尾部后能返回到数组头。参考代码一：见下页参考代码一：见下页#includeusing namespace std;int main()const int Max=
30、10000;int num,m,aMax;while(cinnumm)for(int i=0;inum;i+)ai=i+1;/小孩编号小孩编号 int k=1;/标识处理第标识处理第k个小孩的离开个小孩的离开 int i=-1;/初值初值 while(1)/圈中数圈中数m个小孩个小孩 for(int j=0;jm;)i=(i+1)%num;if(ai!=0)j+;if(k=num)break;/该小孩是最后一个吗？该小孩是最后一个吗？/是，则为胜利者是，则为胜利者 ai=0;/标识该小孩离开标识该小孩离开 k+;/准备处理圈中的准备处理圈中的 /下一个小孩下一个小孩 coutendl;cout
31、 aiendl;/第第ai个小孩获胜个小孩获胜 return 0;分析分析方法二：数学方法方法二：数学方法更改一下更改一下报数的基准，从数的基准，从0开始数，那么开始数，那么这num个小孩一个小孩一字排开，就是：字排开，就是：0，1，2，3，num-1。算法思想是，从唯一的小孩开始（起始他的标号为算法思想是，从唯一的小孩开始（起始他的标号为0），），倒推到倒推到num次这个小孩的标号，最终得到起始状态时共次这个小孩的标号，最终得到起始状态时共有有num个小孩时最终的标号，即为题目所求。个小孩时最终的标号，即为题目所求。以下的推导类似于数学归纳法证明过程：以下的推导类似于数学归纳法证明过程：如果
32、只有一个小孩，他的标号是如果只有一个小孩，他的标号是0，那么这个小孩的标号，那么这个小孩的标号就是结果，此时就是结果，此时r=0。考虑目前有考虑目前有k-1个小孩的情况：个小孩的情况：0，1，2，r-1，r，r+1，k-2，k-1 这里标号这里标号r就是当小孩总数为就是当小孩总数为k-1个的时候最终的结果。个的时候最终的结果。当小孩总数为当小孩总数为k时时 按照新定义的计数方式，从按照新定义的计数方式，从0开始数，数到开始数，数到m-1出列，那么上出列，那么上个数列在这个孩子没出列时的编号是多少呢？如下：个数列在这个孩子没出列时的编号是多少呢？如下：m，m+1，m+2，m+r-1，m+r，m+
33、r+1，m+k-2，m+k-1 两个两个问题需需考考虑：出列的那个小孩没有考虑进去，由于所有小孩是围成一个出列的那个小孩没有考虑进去，由于所有小孩是围成一个圈的，所以，可把标号为圈的，所以，可把标号为m-1的这个出列的小孩放在首尾的这个出列的小孩放在首尾皆可，比如放在前面：皆可，比如放在前面：m-1，m，m+1，m+2，m+r-1，m+r，m+r+1，m+k-2，m+k-1小孩小孩围成个圈，那成个圈，那么么这个个编号号应该是从是从0开始，到开始，到k-1结束束。只要把所有的只要把所有的这些些编号号对k取模即可。新的取模即可。新的r值就按照就按照这个个变换方法方法变换即可，于是得到即可，于是得到
34、r=(r+m)%k。参考代码二参考代码二#include using namespace std;int main()int num,m,rwhile(cinnumm)r=0;for(int k=1;k=num;+k)r=(r+m)%k;coutr+1endl;return 0;5 负数进制转换负数进制转换 问题描述（大意）：问题描述（大意）：设设计计一一个个程程序序，读读入入一一个个十十进进制制数数和和一一个个负负进进制制的的基基数数，并并将将此此十十进进制制数数转转换换成成为为此此负负进进制制下下的的数数：-R-2,-R-2,-3,-4,.-203,-4,.-20 例例如如，十十进进制制数
35、数-15-15，相相当当于于-2-2进进制制数数110001110001：因因110001=1*110001=1*(-2)(-2)5 5+1*(-2)+1*(-2)4 4+0*(-2)+0*(-2)3 3+0*(-2)+0*(-2)2 2+0*(-2)+0*(-2)1 1+1*(-2)+1*(-2)0 0输入输入 输入的每行有两个数据输入的每行有两个数据N N、-R R。N N是是十十进进制制数数，（-32768-32768N N3276732767），-R R是是负负进进制制数数的基数。的基数。输出输出 相相对于于每每组输入入，应输出出此此负进制制数数及及其其基基数数，若若此此基基数超数超过
36、1010，则参照十六参照十六进制的方式制的方式处理。理。输入与输出样例输入与输出样例输入入样例例输出样例输出样例30000 30000 2 2-20000-20000 2 228800 28800 1616-25000-25000 161630000=11011010101110000(base-2)30000=11011010101110000(base-2)-20000=1111011000100000(base-2)-20000=1111011000100000(base-2)28800=19180(base-16)28800=19180(base-16)-25000=7FB8(base
37、-16)-25000=7FB8(base-16)分析分析采用与正数进制的转换相类似的方法。采用与正数进制的转换相类似的方法。对负数进制，每次取的余数保证在对负数进制，每次取的余数保证在0R-1之间，就可以直之间，就可以直接输出。接输出。例如例如-R=-16，则余数应该在，则余数应该在015。所以用模。所以用模“%”运算符的运算符的时候必须注意检查是不是在该范围（可能在时候必须注意检查是不是在该范围（可能在-R+10），否），否则就调整。则就调整。调整的方法是：调整的方法是：if（余数（余数0）余数余数=余数余数+R;商商=商商+1;数码转换表数码转换表char change21=0,1,2,3
38、,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K;#include using namespace std;char change21=0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K;int main()long int r,m,base,i,k;char a1000;while(cinmbase)k=m;memset(a,0,sizeof(a);i=0;while(true)r=m%base;m=m/base;if(r=0;i-)coutai;cout(base base;cout)endl;return 0;任意范围基数转换表任意范围
39、基数转换表char map(int temp)if(temp=9)return 0+temp;elsereturn A+(temp-10);6 数塔问题数塔问题 问题描述问题描述 对任意正整数对任意正整数n n，求由，求由n n层层n n构成的数的个位数。构成的数的个位数。输入输入 输输入入文文件件的的第第1 1行行是是整整数数T T，（0T=500T=50），接接下下来来的的T T行行每每行有一个整行有一个整数数n n，（，（0n=100n=101010）。）。输出输出 对输入中的每个对输入中的每个n，对应于输出中的一行，内容是由，对应于输出中的一行，内容是由n层层n构成的数的个位数。构成的
40、数的个位数。输入与输出样例输入与输出样例输入样例输入样例输出样例输出样例3124235665分析分析设设n的个位数为的个位数为a，即，或，即，或n=10q+a，再设，再设 的个位数的个位数为为A，指数为，指数为m，那么由，那么由 得得 A=。分情况对分情况对a进行讨论：进行讨论：a=091.如果如果a=0，1，5或或6，那么，那么A仍分别为仍分别为0，1，5或或6。2.如果如果a=2，那么，那么21 2，22 4，23 8，24 6，25 2(mod 10)2的幂的幂2t的个位数循环出现，周期是的个位数循环出现，周期是4。如设指数如设指数t=4k+r，r=1，2，3，4，那么，那么2t的个位数
41、仅与的个位数仅与r有关。有关。分析分析(a=2)：只需计算：只需计算m被被4除得的余数。因除得的余数。因n为偶数，所以为偶数，所以m也也为偶数。如果为偶数。如果n本身是本身是2，那么，那么A=4；在其他情况下，；在其他情况下，m的指数是也是偶数的指数是也是偶数2p，此时，此时m能被能被4除尽，即除尽，即r=4。此时。此时A=6。根据根据2.2.类似的讨论，以下简单地讨论：类似的讨论，以下简单地讨论：3.3.如果如果a=3，n=10q+3。再设再设q=2p+s。周期是周期是4。设设m m的指的指数数t=4k+r，r=1，2，3，4。若若s=0，则，则m被被4除的余数是除的余数是3，此时，此时A=
42、7。若若s=1，则，则m被被4除的余数仍是除的余数仍是1，此时，此时A=3。如果如果a=4，周期是周期是2。m是一个偶数，此时是一个偶数，此时A=6。分析分析5.5.如果如果a=7，n=10q+7，周期是周期是4。若若q为奇数，则为奇数，则n被被4除的余数是除的余数是1，A=7。若若q为偶数，则为偶数，则n被被4除的余数是除的余数是3，A=3。5.5.如果如果a=8，n=10q+8，周期是周期是4。幂。幂m的底是的底是n，为偶，为偶数，其指数也是偶数。在这种情况下，数，其指数也是偶数。在这种情况下，A=6。6.6.如果如果a=9，周期是周期是2。A=97 幸运数幸运数 问题描述问题描述 中国人
43、认为中国人认为8 8是一个幸运数字。鲍勃也认为是这样，而且他是一个幸运数字。鲍勃也认为是这样，而且他有他自己的幸运数有他自己的幸运数 L L。现在他要构造他的幸运数，该数是。现在他要构造他的幸运数，该数是仅由数字仅由数字8 8组成且是组成且是L L的倍数中最小的那个正整数。的倍数中最小的那个正整数。输入输入 输输入入有有多多组组测测试试数数据据，每每一一组组仅仅由由一一行行上上的的一一个个正正整整数数L L构构成成，(1=(1=L=L3)因子。因子。Case 1Case 1：L有因子有因子16，那么无法找到这个幸运数，那么无法找到这个幸运数H Case 2 Case 2：L有因子有因子5，那么
44、无法找到这个幸运数，那么无法找到这个幸运数H Case 3 Case 3：L有因子有因子2t(t4)。设。设L=2tm，m为无为无有因子有因子5的的奇数。奇数。Case 3进一步讨论进一步讨论 表明表明 是是m的倍数的倍数 所以有所以有 这里，这里，(9(9m m，10)=110)=1。由欧拉定理，可得由欧拉定理，可得 由由 得得 由于由于k k是所求数的最小长度，因此必有是所求数的最小长度，因此必有Case 3算法算法计算计算9m，并求欧拉函数，并求欧拉函数值值(9m)，记，记M=(9m)。求求M的素因子分解，在的素因子分解，在M的因子中从较小的因子开始作的因子中从较小的因子开始作为为k，尝
45、试验证，尝试验证 。判断：如果成立，那么就找到最小的判断：如果成立，那么就找到最小的k，终止查找。，终止查找。8 哥德巴赫猜想哥德巴赫猜想 问题描述问题描述 哥哥德德巴巴赫赫是是一一位位德德国国的的业业余余数数学学家家。17421742年年，他他写写信信给给当当时的数学家欧拉，信中提出如下猜想：时的数学家欧拉，信中提出如下猜想：每个大于每个大于4 4的偶数都可以写成两个奇素数之和。的偶数都可以写成两个奇素数之和。例如：例如：8=3+58=3+5，3 3 和和5 5都是奇素数，都是奇素数，20=3+17=7+1320=3+17=7+13 42=5+37=11+31=13+29=19+23.42=
46、5+37=11+31=13+29=19+23.直到现在，仍未证明该猜想是否是真的。不管怎样，你的直到现在，仍未证明该猜想是否是真的。不管怎样，你的任务是对于任务是对于100100万以内的偶数验证哥德巴赫猜想。万以内的偶数验证哥德巴赫猜想。输入输入 有有多多组组测测试试数数据据，每每组组测测试试数数据据由由一一个个偶偶数数n n构构成成（66n n 1000000 1000000）。）。当输入是当输入是0 0时表示输入结束。时表示输入结束。输出输出 对每种每种测试数据，数据，输出形如出形如n n=a a+b b的表达式，其中的表达式，其中a a和和b b是奇素数，加号是奇素数，加号应该用空格隔开
47、，如下面的用空格隔开，如下面的输出出样例。例。如果有多如果有多对奇素数奇素数满足，足，仅取差取差b b a a最大的一最大的一组。如果。如果没有没有这样的素数的素数对，那么，那么输出出“Goldbachs conjecture Goldbachs conjecture is wrong.is wrong.”输入与输出样例输入与输出样例输入样例输入样例 820420 输出样例输出样例 8=3+520=3+1742=5+37分析分析对于偶数对于偶数n，可以取不大于，可以取不大于n/2/2的奇数的奇数p，记，记q=n-p，即写，即写n=p+q。本题测试数据较弱，可用常规的判定素数的本题测试数据较弱，
48、可用常规的判定素数的埃拉托色尼埃拉托色尼筛法筛法做，直接做，直接判定判定p和和q是否为素数。是否为素数。为求满足差为求满足差ba最大的一组，只要从最大的一组，只要从3 3开始到不大于开始到不大于n/2/2的的奇数依次作为奇数依次作为p。当。当n10000001000000时，采用常规方法，有超时，采用常规方法，有超时的可能。时的可能。也可尝试用也可尝试用Miller-RabinMiller-Rabin素数测试素数测试该算法并不能保证待测整数一定是素数，但对素数测试该算法并不能保证待测整数一定是素数，但对素数测试的正确性随着测试次数的增加而增加。以下程序中采用的正确性随着测试次数的增加而增加。以
49、下程序中采用了二次测试。了二次测试。练习：四个素数之和问题练习：四个素数之和问题欧拉证明素数有无穷多个。但每个整数能表示成四个素数欧拉证明素数有无穷多个。但每个整数能表示成四个素数之和吗？我也不知道这一答案，希望你能帮助我。我希望之和吗？我也不知道这一答案，希望你能帮助我。我希望你能高效率地解决这一问题。你能高效率地解决这一问题。输入：每行输入一个整数输入：每行输入一个整数N（N=10000000），它是你需），它是你需要把它表示成四个素数之和的数。输入直到文件结束为止。要把它表示成四个素数之和的数。输入直到文件结束为止。输出：对于每个输入行都有一个输出行，每行包含符合要输出：对于每个输入行都
50、有一个输出行，每行包含符合要求的四个素数。如果该数不能表示为四个素数之和，那么求的四个素数。如果该数不能表示为四个素数之和，那么输出一行输出一行“Impossible.”。也可能有多组解，任何合理的。也可能有多组解，任何合理的解都将被接受。解都将被接受。输入与输出举例输入与输出举例输入样例输入样例243646 输出样例输出样例3 11 2 73 7 13 1311 11 17 79 for循环语句执行次数循环语句执行次数问题描述问题描述有一个C语言型的for循环语句：for(j=0;(j-b)%p!=0;j+=a)statement;即该循环中循环变量j的初值为0，只要(j-b)%p不等于0就
