1、1Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009ACM training-Number Theory Outline GCD and LCMModulo arithmetic Prime numbers Number theory functions Prime factorization Congruence equations Continued fraction2Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 GCD and LCMDefin

2、ition 1: (x1, x2, , xn) and x1, x2, , xn denotes the greatest common divisor(GCD) and the least common multiple(LCM), respectively, of n positive integers x1, x2, , xn.How to compute GCD and LCM?(a,b)=(b, a mod b) b0a b=0 (1)where a, bN and N denotes the nature number set.3Hongyu Zhao(趙宏宇) School of

3、 Inform. Sci. and Tech. 07/20/2009 , ( , )a ba ba b(2)121234(,)(,),),),)nnx xxx xxxx(3)121234,nnx xxx xxxx(4)Example 1: (24, 72, 108, 32) =(24,72), 108), 32) =(24, 108), 32) =(12, 32) =424, 72, 108, 32=24,72, 108, 32=72, 108, 32=216, 32=864 GCD and LCM(cont. 1)4Hongyu Zhao(趙宏宇) School of Inform. Sci

4、. and Tech. 07/20/2009Sample C+ program 1: The text file of a1.txt provides several positive integers as well as 0 in the end. Output the GCD and LCM of these positive integers.Sample Input: 24 72 108 32 0 Output: 4 864C+ source program: GCD and LCM(cont. 2)5Hongyu Zhao(趙宏宇) School of Inform. Sci. a

5、nd Tech. 07/20/2009#include #include using namespace std;void main() int x,y,gcd=0, lcm=1, t; ifstream f(a1.txt); if(!f) couta1.txt open error.x; if(x=0) break; / initiation: (0, x)=x 1,x=x y=x; while(x!=0) t=gcd%x; gcd=x; x=t; /(gcd, x) x=y;y=lcm;lcm*=x; /lcm, x while(x!=0) t=y%x; y=x; x=t; lcm/=y;

6、 coutgcd lcmendl; f.close(); GCD and LCM(cont. 3)6Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009Algorithm description: gcd0; lcm1; repeating the following steps: 1) read x; if x=0 then stop; otherwise perform 2)4); 2) gcd(gcd, x); /due to Eq. (3) 3) lcm(lcm, x); /due to Eq. (4) 4) goto

7、 1). GCD and LCM(cont. 4 over)7Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmeticDefinition 1: Given two integer numbers a and b, the operators +k and k, where k is a positive integer, are defined by the following modulo arithmetic expressions, respectively.() mod () mod

8、kkababkababk(1)(2)Properties of +k and k:a) commutative law: b) associative law: , kkkkabba abba()()kkkkabcabc()()kkkkabcabc8Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 1)c) k is assignable to +k:d) ()()()kkkkkabcabbc( mod )( mod )( mod )( mod )kkkkabakbkabak

9、bk1212() mod ( mod )( mod )( mod )nkkknaaakakakak1212() mod ( mod )( mod )( mod )nkkknaaakakakake)f) mod ( 1 mod )( mod )( mod )kakkakkak mod ( mod ) mod bbakakk9Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 2)Theorem 1: If are integers not all of which are zer

10、o and d denotes , then given any integer l, the equation12,na aa12(,)na aa1 122nna xa xa xlhas integer solutions, if and only if (iff) d|l (represents d can divide l).(3)Corollary 1: If d|l, Eq. (3) is equivalent to1212.nnaaalxxxdddd(4)10Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009Pr

11、oof: Modulo arithmetic(cont. 3)Corollary 2: If (a1,a2)=d and d|l, all the solutions of can be represented as211122axxtdaxxtdwhere and satisfy1 122a xa xl()tI(6)1x2x1 122.a xa xl11222121 1221221(/)(/)() /a xa t daxa t da xa xa aa a t dl(5)11Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009

12、 Modulo arithmetic(cont. 4)Example 1: Obtain the integer solutions of 60 x-134y=8.Answer: (60, 134)=2 and 2|8, integer solutions exist. 60 x-134y=8 30 x-67y=4. First, we find an integer solution of 30 x-67y=1. 30=130+067 67=030+167 (30, 67) 30=067+30 30=30-067=130+067 =(67, 30) 67=230+7 7=67-230=-23

13、0+167 =(30, 7) 30=47+2 2=30-47=930-467 =(7, 2)=1 7=32+1 1=7-32=-2930+1367Thus, x=-29 and y=-13 is a solution of 30 x-67y=1; x=-116 and y=-52 is a solution of 30 x-67y=4.12Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 5)As result, 116675230 xtyt (tI) The Eq. (5)

14、 in Corollary 2 is called linear Diophantine. In Example 1, the method to obtain one solution of (5) is Euclidean algorithm. Another method is continued fraction. The Euclidean algorithm is given as follows.13Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 6)Eucl

15、idean algorithm for finding one solution of linear Diophantine:Input: a, b, nOutput: If solution does not exist, output no solution; otherwise, output one solution for x, y.1) read a, b, n;2) s1sign(a); s2sign(b); aabs(a); babs(b); 3) dgcd(a, b); 4) if (n mod d)0, then output no solution and stop; o

16、therwise, do 5)5) aa/d; bb/d; nn/d;axbyn14Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/20096) x01; y00; x0; y1; 7) r(a mod b); t=a div b; ab; br;8) x1-t*x; y1-t*y; x1x1+x0; y1y1+y0;9) x0 x; y0y; xx1; yy1;10) if r=1, then goto 11) otherwise goto 7);11) xs1*x*n; ys2*y*n;12) output x, y and

17、stop.Sample C+ program 1:#include using namespace std;#include math.hvoid main() Modulo arithmetic(cont. 7)15Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 8) int a, b, d, n, s1, s2, t, r, x0, y0, x, y, x1, y1; coutabn; s1=a0?1:-1; s2=b0?1:-1; a=abs(a); b=abs(b)

18、; x=a; y=b; while(y!=0) r=x%y; x=y; y=r; d=x; if(n%d!=0) coutNo solution.n; return; a/=d; b/=d; n/=d; x0=1; y0=0; x=0; y=1; while(1) r=a%b; t=a/b; a=b; b=r; x1=-t*x; y1=-t*y; x1+=x0; y1+=y0; x0=x; y0=y; x=x1; y=y1; if(r=1) break; 16Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo

19、arithmetic(cont. 9) x=s1*x*n; y=s2*y*n; coutx yendl; 17Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 10)Theorem 2: Given any integers a, b and positive integer k, if b|a and (b, k)=1, the modulo arithmetic (a/b) mod k can be computed as( / ) mod () mod a bkA ak

20、(7)where A satisfies 1.A bB kProof: Supposing a/b=s, one can obtain a=bs. In terms Theorem 1 and (b, k)=1, there exist integers A and B satisfy 1.A bB k18Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 11)()()1() mod .A aAb sA bsB kssB k ssA ak Therefore, Example

21、 2: Using Theorem 2 for computing (108/12) mod 5.Answer: Since 312-75=1, (108/12) mod 5 =(3108) mod 5 =(33) mod 5 =4. 19Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 12)Algorithm for an exponential value with modulo arithmetic: ( mod )byak(8)where a, b, k are p

22、ositive integers and b is a large number. Using binary representation, b is denoted by vector12210,nnbbb b b(9)where bi0, 1, i=0, 1, , n-1, and all bi satisfy121210222.nnnnbbbbb(10)20Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 13)As result, 12121022221 = mod

23、nnnniiibbbbbbbaaak (11)In (11), can be recursively computed within at most n multiplication and modulo operations, where n= log2b , since 21222, mod nna aaak012222 0 1,2,1iiaaiaain(12)21Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 14)ACM exercise 1: Computing

24、the following expression.1212(+) mod HBBBHyAAAMwhere (1M45000), (1H45000), (1Ai, Bi231).Input: The first line of the input file is Z. Underneath there are Z data segments. In each data segment, the first line is M and the second line is H, followed by H lines, each of which contains two integer numb

25、ers Ai and Bi. Output: For each data segment, output y.22Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 15)Sample Input: 3 16 4 2 3 3 4 4 5 5 6 36123 1 2374859 3029382 45000 1 2147483648 2147483647Output: 2 13195 3087223Hongyu Zhao(趙宏宇) School of Inform. Sci. an

26、d Tech. 07/20/2009 Modulo arithmetic(cont. 16)#include /C+ source program #include using namespace std;void main() ifstream f(a2.txt); unsigned long A, B, H, M, Z, y, i, j, k, t, r; if(!f) coutZ; for(i=1;iMH; y=0; for(j=1;jAB; t=1; r=A%M; for(k=0; k=1; y=(y+t)%M; / end H loop coutyendl; /end Z loop

27、/end main Modulo arithmetic(cont. 17)25Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 18 over)Exercise: Input file contains several lines. Each line provides two positive integers a and b (a, b231), output the last two digits of decimal representation of ab for

28、each input line.Sample input: 2 8 17 10Sample output: 56 4926Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime numbersPrime number distribution:Theorem 1: Let (n) denote the number of prime numbers less than or equal to n, (n) satisfylim ( )nn ( )lim0nnn( )lim1/ln( )nnnn(1)(2)(3)27H

29、ongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime numbers(cont. 1)Mersenne prime numbers: 21ppM(4)where p is a prime number. If Mp is a prime number, it is called Mersenne prime number. Till 2008, only 46 Mersenne primes have been found! Is there infinite number of Mersenne primes?Fe

30、rmat prime numbers:221 (0)nnFn(5)If Fn is a prime number, it is called Fermat prime number.28Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime numbers(cont. 2)Sieve method: Given any positive integer n, if no integer within can divide n, n is prime.Algorithm to generate an array sto

31、ring all primes less than or equal to n(n3):2ninput n; /suppose array p enough to store primesk=1; p0=2; for(a=3;a=n; a+=2) b=(int)sqrt(a+1.0); for(j=1;jk&pj=k|pjb) pk+=a;29Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime numbers(cont. 3)ACM exercise 2: The distance of prime nu

32、mbers Your program accepts two positive integers L and U (1LU231) and finds the minimum and maximum distances between two adjacent primes in the range of LU. Output the first pairs of primes generating the minimum and maximum distances. Input: Each line of input file provides two positive integers L

33、 and U, where U-L1000000.Output: If there is no adjacent two primes within LU, output a line as There are no adjacent primes, otherwise, output two required pairs of primes.30Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime numbers(cont. 4)Sample input: 2 1714 17Output: 2,3 are clo

34、sest,7,11 are most distant.There are no adjacent primes.31Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime numbers(cont. 5)Algorithm description:1) Store all primes into an array with length of /actual 47922) read L, U; dmin=2147483647; dmax=0; 3) a=find_prime(L, U); /find the firs

35、t prime in LU4) if a=0, then goto 10); otherwise do 5);5) b=find_prime(a+1, U); if b=0, then goto 10);6) d=b-a;7) if ddmin then a1=a; b1=b; dmax=d; 9) a=b; goto 5);3124634131311.22/ln25175;32Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/200910) if dmax=0, then output no primes; otherwise o

36、utput a0, b0, a1, b1;11) stop./C+ source program:#include #include using namespace std;#include unsigned long p5175, k; Prime numbers(cont.6)33Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime numbers(cont.7)unsigned find_prime(unsigned L, unsigned U) unsigned a,b;int j; if(L=2) ret

37、urn L; for(a=(L&1)=1?L:L+1;a=U;a+=2) b=(unsigned int)sqrt(a+1.0); for(j=1;jk&pj=k|pjb) break; return aU?0:a;34Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime numbers(cont.8)void main() unsigned a,b,j,n=46341; k=1;p0=2; for(a=3;a=n; a+=2) b=(int)sqrt(a+1.0); for(j=1;jk&

38、pj=k|pjb) pk+=a; ifstream f(a3.txt); unsigned L,U,a0,b0,a1,b1,d,dmin,dmax; if(!f) coutLU;if(f.eof() break; dmin=2147483647;dmax=0; a=find_prime(L,U); if(a!=0) while(1) b=find_prime(a+1,U);if(b=0) break; d=b-a; if(ddmax) a1=a;b1=b;dmax=d; a=b;36Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/

39、2009 Prime numbers(cont.10 over)if(dmax=0) coutThere are no adjacent primes.n; else couta0,b0 are closest, a1,b1 are most distant.endl; coutendl;37Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Number theory functionsDefinition 1: Let I+ and C* denotes the set of positive integers and

40、complex numbers, respectively, the function f: I+C* is called number theory function or arithmetic function.Definition 2: A number theory function is called multipliable if (m, n)=1 and f(mn)=f(m)f(n).Theorem 1: Supposing positive integer n has its standard prime factorization as 1ikeiinp(1)38Hongyu

41、 Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Number theory functions(cont. 1)a. the number of positive factors of n is computed by1( )(1)kiine(2)b. the summation of positive factors of n is computed by111( )1iekiiipnp(3)c. the number of positive integers less than n and relatively prime to

42、 n is computed by11( )1kiinnp(4)Euler functiond. (n), (n) and (n) are multipliable.39Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Number theory functions(cont. 2)Example 1: n=24=233, thus p1=2, p2=3, e1=3, e2=1all the positive factors are:1, 2, 3, 4, 6, 8, 12, 24 (8 terms)all the rel

43、atively prime numbers to 24 within 124 are:1, 5, 7, 11, 13, 17, 19, 23 (8 terms) 4221 31( )15 4601234681224213 1n 111 2( )2411248232 3n ( )(3 1) (1 1)8n40Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Number theory functions(cont. 3)Theorem 2(Euler Theorem): Supposing m is a positive i

44、nteger and (a, m)=1, the equation below is hold.()1 (mod )mam(5)If m=p, and p is a prime, then (m)=p-1 and 11 (mod )pap(6)Fermat small TheoremTheorem 3(Wilson Theorem): If p is a prime number, then (1)!1 (mod )pp (7)41Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Number theory functio

45、ns(cont. 4)Theorem 4: Given any prime number p, the following modulo arithmetic is hold. mod ( -1) mod mod bbpapap(8)Please try to prove this theorem at the lecture.42Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Number theory functions(cont. 5)ACM exercise 1: Happy 2004 Given any pos

46、itive integer X, let S be the summation of all factors dividing 2004X, output the value of S modulo 29.Input: Several X at separated line. (1X10000000)Output: One result in one line.Algorithm analysis: 2004X=22X3X167X, thus211121 31 1671.213 11671332XXXYS43Hongyu Zhao(趙宏宇) School of Inform. Sci. and

47、 Tech. 07/20/2009 Number theory functions(cont. 6) Since (332, 29)=1, due to modulo arithmetic Theorem 2, , where A satisfies A332+B29=1.It can be found that A=9, B=-103. Therefore, S=(9Y) mod 29. The key problem is computing Y mod 29. mod 29SA Y2111(21) mod 28(1) mod 28(1) mod 28 mod 29(21) (31) (1

48、671) mod 29 = 22832816728 mod 29XXXXXXY Theorem 4.44Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Number theory functions(cont. 7)C+ source program:#include #include using namespace std;void main() unsigned Y,S,X,r,i,k,t1,t2,t3; ifstream f(A4.TXT); if(!f) coutX;if(f.eof() break; 45Hon

49、gyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Number theory functions(cont. 8 over) r=X%28; t1=t2=t3=1; k=(2*r+1)%28; for(i=1;i=k;i+) t1=(t1*2)%29; k=(r+1)%28; for(i=1;i=k;i+) t2=(t2*3)%29;t3=(t3*167)%29; t1=(t1+28)%29;t2=(t2+28)%29;t3=(t3+28)%29; Y=(t1*t2*t3)%29; S=(9*Y)%29; coutSk. The

50、 so-called prime factorization is used for producing every prime number pi dividing integer n as well as every corresponding exponential ei satisfying .|ieipn47Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime factorization(cont. 1)Algorithms for prime factorization:Algorithm 1: Con

51、tinuously dividing from 2. Sample input: 756，Output: 2 2 3 3 3 71) k=2;2) if k=n, then do 3); otherwise stop;3) if k|n,then output k; n=n/k; goto 2) ; otherwise do 4);4) k+;goto 2)(參考趙宏宇精通C程序設計教程第4章)Advantages: without prime number test;efficient for n containing small prime factors;Disadvantage: Th

52、e maximum time complexity is O(n), if n is a prime number.48Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime factorization(cont. 2)Algorithm 2: Brute Force method. Sample input: 756，Output: 2 2 3 3 3 7For 4-byte integer data type:1) Generating all primes and store them in p array;

53、2) i=0; (totally 4792 primes)3) if pi= then do 4); otherwise stop;4) if pi|n, then output pi; n=n/pi; goto 3) ; otherwise do 5);5) i+;goto 3)312n49Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime factorization(cont. 3)Prime factorize n!Theorem 1: Given positive integer n and prime

54、p, if represents the integer satisfying , then ( , )p n( , )| !p npn1( , )jjnp np(2)Thus, ( , )!p np nnp(3)Note: All prime factors of n! are primes less than or equal to n.50Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime factorization(cont. 4)Example 1: factorize 10!.Answer: All

55、primes less than 10 are 2, 3, 5, 7.101010(2,10)52182481010(3,10)3 14391010(5,10)2, (7,10)157 Thus, 10!=3628800=2834527.51Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime factorization(cont. 5)ACM exercise 1: Considering a positive integer n, how many continuous zeros in the most ri

56、ght of the decimal representation of n! ?For example: 3!=6, there is 0 zero in the most right. 10!=3628800, there are 2 zeros in the most right.Input: Several values of n in separated lines. (0 n231)Output: The number of specified zeros in separated lines.Sample input: 4 20 2147483647Sample output:

57、0 4 536870902 52Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime factorization(cont. 6)Algorithm design: 1) read n;2) Compute k1=(2, n) and k2=(5, n);3) Output min(k1,k2);4) Stop.Computing (p, n): /n 0k=0; s=(double)n;2) s=s/p;3) i=(int)s; if(i=0) goto 5); otherwise do 4);4) k+=i;

58、goto 2);5) return k;53Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime factorization(cont. 7)#include /C+ source progam#include using namespace std;unsigned alpha(unsigned p,unsigned n) double s=n;unsigned k=0,i; if(n=0) return 0; while(1) s/=p;i=(int)s;if(i=0) break; k+=i; return

59、k;54Hongyu Zhao(趙宏宇) School of Inform. Sci. and Tech. 07/20/2009 Prime factorization(cont. 8 over)void main() unsigned n,k1,k2; ifstream f(A5.TXT); if(!f) coutn;if(f.eof() break; /k1=alpha(2,n); /k1 is always greater than k2 k2=alpha(5,n); coutk2endl; 55Hongyu Zhao(趙宏宇) School of Inform. Sci. and Te

60、ch. 07/20/2009 Congruence equationsDefinition 1: ab (mod m) represents (a mod k)=(b mod k), which is called a and b are congruent with modulo m.Properties: m is positive integera. ab (mod m) k|(a-b)b. If acbc (mod m), then , particularly, if (c,m)=1, ab (mod m).c. Given any positive integer d, ab (mod m), iff. adb