acm-training-number-theory數(shù)論

1、ACM training-Number Theory,Outline,GCD and LCMModulo arithmetic Prime numbers Number theory functions Prime factorization Congruence equations Continued fraction,GCD and LCM,Definition 1: (x1, x2, …, xn) and [x1, x

2、2, …, 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) b?0,a

3、 b=0,(1),where a, b?N and N denotes the nature number set.,(2),(3),(4),Example 1: (24, 72, 108, 32) =(((24,72), 108), 32) =((24, 108), 32) =(12, 32)

4、 =4,[24, 72, 108, 32]=[[[24,72], 108], 32]=[[72, 108], 32]=[216, 32]=864,GCD and LCM(cont. 1),Sample C++ program 1: The text file of a1.txt provides several positive integers as well as 0 in the end.

5、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),#include #include using namespace std;void main(){ int x,y,

6、gcd=0, lcm=1, t; ifstream f("a1.txt"); if(!f) { cout>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;

7、 //[lcm, x] while(x!=0) { t=y%x; y=x; x=t; } lcm/=y; } cout<<gcd<<" "<<lcm<<endl; f.close();},GCD and LCM(cont. 3),Algorithm descr

8、iption: gcd?0; lcm?1; 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)

9、 lcm?(lcm, x); //due to Eq. (4) 4) goto 1).,GCD and LCM(cont. 4 over),Modulo arithmetic,Definition 1: Given two integer numbers a and b, the operators +k and ?k, where k is a positive integer, are defined

10、 by the following modulo arithmetic expressions, respectively.,(1),(2),Properties of +k and ?k:a) commutative law: b) associative law:,Modulo arithmetic(cont. 1),c) ?k is assignable to +k:d),e)f),Modulo arithmetic(co

11、nt. 2),Theorem 1: If are integers not all of which are zero and d denotes , then given any integer l, the equation,has integer solutions, if and only if (iff) d|l (represents d ca

12、n divide l).,(3),Corollary 1: If d|l, Eq. (3) is equivalent to,(4),Proof:,Modulo arithmetic(cont. 3),Corollary 2: If (a1,a2)=d and d|l, all the solutions of can be represented as,,where and

13、 satisfy,(6),(5),Modulo arithmetic(cont. 4),Example 1: Obtain the integer solutions of 60x-134y=8.Answer: (60, 134)=2 and 2|8, integer solutions exist. 60x-134y=8 ? 30x-67y=4. First, we find an integer solu

14、tion of 30x-67y=1. 30=1?30+0?67 67=0?30+1?67 (30, 67) 30=0?67+30 30=30-0?67=1?30+0?67 =(67, 30) 67=2?30+7 7=67-2

15、?30=-2?30+1?67 =(30, 7) 30=4?7+2 2=30-4?7=9?30-4?67 =(7, 2)=1 7=3?2+1 1=7-3?2=-29?30+13?67Thus, x=-29 and y=-13 is a solution of 30x-67y=1; x=-116 and y=-52 is a solution of 30x-6

16、7y=4.,Modulo arithmetic(cont. 5),As result,,,(t?I),The Eq. (5) 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 fract

17、ion. The Euclidean algorithm is given as follows.,Modulo arithmetic(cont. 6),Euclidean algorithm for finding one solution of linear Diophantine:Input: a, b, nOutput: If solution does not exist, output no solution;

18、 otherwise, output one solution for x, y.read a, b, n;s1?sign(a); s2?sign(b); a?abs(a); b?abs(b); d?gcd(a, b); if (n mod d)?0, then output no solution and stop; otherwise, do 5)5) a?a/d; b?b/d; n?n/

19、d;,6) x0?1; y0?0; x?0; y?1; 7) r?(a mod b); t=a div b; a?b; b?r;8) x1?-t*x; y1?-t*y; x1?x1+x0; y1?y1+y0;9) x0?x; y0?y; x?x1; y?y1;10) if r=1, then goto 11) otherwise goto 7);11) x?s1*x*n; y?s2*y*n;12) output x, y a

20、nd stop.Sample C++ program 1:#include using namespace std;#include "math.h"void main(),Modulo arithmetic(cont. 7),Modulo arithmetic(cont. 8),{ int a, b, d, n, s1, s2, t, r, x0, y0, x, y, x1, y1; cout>

21、;a>>b>>n; s1=a>0?1:-1; s2=b>0?1:-1; a=abs(a); b=abs(b); x=a; y=b; while(y!=0) { r=x%y; x=y; y=r; } d=x; if(n%d!=0) { cout<<"No solution.\n"; return; } a/=d; b/=d; n/=d; x0=1

22、; 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; },Modulo arithmetic(cont. 9),x=s1*x*n; y=s2*y*n; cout<&

23、lt;x<<" "<<y<<endl;},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,(7),wher

24、e A satisfies,Proof: Supposing a/b=s, one can obtain a=b·s.,In terms Theorem 1 and (b, k)=1, there exist integers A and B satisfy,Modulo arithmetic(cont. 11),Therefore,,Example 2: Using Theorem 2 for computing

25、 (108/12) mod 5.Answer: Since 3?12-7?5=1, (108/12) mod 5 =(3?108) mod 5 =(3?3) mod 5

26、 =4.,Modulo arithmetic(cont. 12),Algorithm for an exponential value with modulo arithmetic:,(8),where a, b, k are positive integers and b is a large number. Using binary representation, b is denoted

27、 by vector,(9),where bi?{0, 1}, i=0, 1, …, n-1, and all bi satisfy,(10),Modulo arithmetic(cont. 13),As result,,(11),In (11), can be recursively computed within at most n multip

28、lication and modulo operations, where n= ?log2b?, since,,(12),Modulo arithmetic(cont. 14),ACM exercise 1: Computing the following expression.,where (1?M?45000), (1?H?45000), (1?Ai, Bi?231).Input: The first line of the i

29、nput 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 numbers Ai and Bi. Output: For each data

30、 segment, output y.,Modulo arithmetic(cont. 15),Sample Input: 3 16 4 2 3 3 4 4 5 5 6 36123 1 2374859 3029382 45000 1 2147483648 2147483647,Output: 2

31、13195 30872,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) { co

32、ut>Z; for(i=1;i>M>>H; y=0; for(j=1;j<=H; j++),{ f>>A>>B; t=1; r=A%M; for(k=0; k>=1; } y=(y+t)%M; } // end H loop cou

33、t<<y<<endl; } //end Z loop} //end main,Modulo arithmetic(cont. 17),Modulo arithmetic(cont. 18 over),Exercise: Input file contains several lines. Each line provides two positive integers a and b (a, b&l

34、t;231), output the last two digits of decimal representation of ab for each input line.Sample input: 2 8 17 10Sample output: 56 49,Prime numbers,Pri

35、me number distribution:Theorem 1: Let ?(n) denote the number of prime numbers less than or equal to n, ?(n) satisfy,(1),(2),(3),Prime numbers(cont. 1),Mersenne prime numbers:,(4),where p is a prime number. If Mp is a pr

36、ime number, it is called Mersenne prime number. Till 2008, only 46 Mersenne primes have been found! Is there infinite number of Mersenne primes?Fermat prime numbers:,(5),If Fn is a prime number, it is called Fer

37、mat prime number.,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 storing all primes less than or equal to n(n?3

38、):,input n; //suppose array p enough to store primesk=1; p[0]=2; for(a=3;a=k||p[j]>b) p[k++]=a;},Prime numbers(cont. 3),ACM exercise 2: The distance of prime numbers Your program accepts two positive integers L a

39、nd U (1?L<U<231) and finds the minimum and maximum distances between two adjacent primes in the range of L~U. Output the first pairs of primes generating the minimum and maximum distances. Input: Each line of inpu

40、t file provides two positive integers L and U, where U-L?1000000.Output: If there is no adjacent two primes within L~U, output a line as "There are no adjacent primes", otherwise, output two required pairs of

41、primes.,Prime numbers(cont. 4),Sample input: 1714 17Output: 2,3 are closest,7,11 are most distant.There are no adjacent primes.,Prime numbers(cont. 5),Algorithm description:Store all primes?

42、 into an array with length of //actual 4792read L, U; dmin=2147483647; dmax=0; a=find_prime(L, U); //find the first prime in L~Uif a=0, then goto 10); otherwise do 5);5) b

43、=find_prime(a+1, U); if b=0, then goto 10);6) d=b-a;if ddmin then { a1=a; b1=b; dmax=d; }a=b; goto 5);,10) if dmax=0, then output …no primes…; otherwise output a0, b0, a1, b1;11) stop.//C++ source program:

44、#include #include using namespace std;#include unsigned long p[5175], k;,Prime numbers(cont.6),Prime numbers(cont.7),unsigned find_prime(unsigned L, unsigned U){ unsigned a,b;int j; if(L==2) return L; for(a=(L&a

45、mp;1)==1?L:L+1;a=k||p[j]>b) break; } return a>U?0:a;},Prime numbers(cont.8),void main(){ unsigned a,b,j,n=46341; k=1;p[0]=2; for(a=3;a=k||p[j]>b) p[k++]=a; } ifstream f("a3.txt"); unsig

46、ned L,U,a0,b0,a1,b1,d,dmin,dmax; if(!f) { cout<<"input file a3.txt not found.\n";return; },Prime numbers(cont.9),while(1) { f>>L>>U;if(f.eof()) break; dmin=2147483647;dmax=0; a=fin

47、d_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;},Prime numbers(cont.10 over),if(dmax==0) cout<<"There are no adjacent pri

48、mes.\n"; else cout<<a0<<","<<b0<<" are closest," \ <<a1<<","<<b1<<" are most distant."<<endl; } c

49、out<<endl;},Number theory functions,Definition 1: Let I+ and C* denotes the set of positive integers and complex numbers, respectively, the function f: I+?C* is called number theory function or arithmetic function

50、.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,(1),Number theory functions(cont. 1),a. the

51、number of positive factors of n is computed by,(2),b. the summation of positive factors of n is computed by,(3),c. the number of positive integers less than n and relatively prime to n is computed by,(4),Euler function,d

52、. ?(n), ?(n) and ?(n) are multipliable.,Number theory functions(cont. 2),Example 1: n=24=23?3, 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 relatively prime numbers

53、 to 24 within 1~24 are:1, 5, 7, 11, 13, 17, 19, 23 (8 terms),Number theory functions(cont. 3),Theorem 2(Euler Theorem): Supposing m is a positive integer and (a, m)=1, the equation below is hold.,(5),If m=p, and p is a

54、 prime, then ?(m)=p-1 and,(6),Fermat small Theorem,Theorem 3(Wilson Theorem): If p is a prime number, then,(7),Number theory functions(cont. 4),Theorem 4: Given any prime number p, the following modulo arithmetic is hold

55、.,(8),Please try to prove this theorem at the lecture.,Number theory functions(cont. 5),ACM exercise 1: Happy 2004 Given any positive integer X, let S be the summation of all factors dividing 2004X, output the value of

56、 S modulo 29.Input: Several X at separated line. (1?X?10000000)Output: One result in one line.Algorithm analysis: 2004X=22X?3X?167X, thus,Number theory functions(cont. 6),Since (332, 29)=1, due to modulo arithmetic Th

57、eorem 2, , where A satisfies A?332+B?29=1.It can be found that A=9, B=-103. Therefore, S=(9?Y) mod 29. The key problem is computing Y mod 29.,,,,,,,Theorem 4.,Number theory functions(cont.

58、 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) { cout>X;if(f.eof()) break;,Number theory functions(cont. 8 over

59、),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;

60、S=(9*Y)%29; cout<<S<<endl; }},Prime factorization,Definition 1: Given positive integers a, k and n, the following expression represents that k is the maximum integer satisfying ak|n.,(1),Namely, ak|n a

61、nd ai?n for i>k. The so-called prime factorization is used for producing every prime number pi dividing integer n as well as every corresponding exponential ei satisfying .,Prime factorization(cont. 1),Al

62、gorithms for prime factorization:Algorithm 1: Continuously 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

63、 do 4);4) k++;goto 2)(參考趙宏宇《精通C程序設(shè)計(jì)教程》第4章)Advantages: without prime number test;efficient for n containing small prime factors;Disadvantage: The maximum time complexity is O(n), if n is a prime number.,Prime factori

64、zation(cont. 2),Algorithm 2: Brute Force method. Sample input: 756，Output: 2 2 3 3 3 7For 4-byte integer data type: Generating all primes? and store them in p array; i=0; (totally 4792 prime

65、s)3) if p[i]<= then do 4); otherwise stop;4) if p[i]|n, then {output p[i]; n=n/p[i]; goto 3) }; otherwise do 5);5) i++;goto 3),Prime factorization(cont. 3),Prime factorize n!Theorem 1: Given positive in

66、teger n and prime p, if represents the integer satisfying , then,(2),Thus,,(3),Note: All prime factors of n! are primes less than or equal to n.,Prime factorization(cont. 4),Example 1: fac

67、torize 10!.Answer: All primes less than 10 are 2, 3, 5, 7.,Thus, 10!=3628800=28·34·52·7.,Prime factorization(cont. 5),ACM exercise 1: Considering a positive integer n, how many continuous zeros in the mos

68、t right 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?n<231)

69、Output: The number of specified zeros in separated lines.,Sample input: 4 20 2147483647,Sample output: 0 4 5368

70、70902,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;i=(int)s; if(i==0) goto 5); oth