ACM-training-number-theory数论.ppt

1、1Hongyu Zhao(赵宏宇 ) School of Inform. Sci. and Tech. 07/20/2009ACM training-Number TheoryOutline 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 LCMDefi

2、nition 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

3、of Inform. Sci. and Tech. 07/20/2009(2)(3)(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. and Tech. 07/20/2009Sample C+ program 1:The text file of a1.txt p

4、rovides 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 0Output: 4 864C+ source program: GCD and LCM(cont. 2)5Hongyu Zhao(赵宏宇 ) School of Inform. Sci. and Tech. 07/20/2009#include #include using namespace std;void main()

5、 int x,y,gcd=0, lcm=1, t; ifstream f(“a1.txt“);if(!f) coutx; if(x=0) break; / initiation: (0, x)=x 1,x=xy=x; while(x!=0) t=gcd%x; gcd=x; x=t; /(gcd, x)x=y;y=lcm;lcm*=x; /lcm, xwhile(x!=0) t=y%x; y=x; x=t; lcm/=y;coutgcd“ “lcmendl; f.close(); GCD and LCM(cont. 3)6Hongyu Zhao(赵宏宇 ) School of Inform. S

6、ci. 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 1). GCD and LCM(cont. 4 over)7Hongyu Zhao(赵宏宇 ) School of Inform. Sci. and Tech. 07/20/2009

7、 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.(1)(2)Properties of +k and k:a) commutative law: b) associative law: 8Hongyu Zhao(赵宏宇 ) School of Inform.

8、 Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 1)c) k is assignable to +k:d) e)f) 9Hongyu Zhao(赵宏宇 ) School of Inform. Sci. and Tech. 07/20/2009 Modulo arithmetic(cont. 2)Theorem 1: If are integers not all of which are zero and d denotes , then given any integer l, the equationhas integer soluti

9、ons, if and only if (iff) d|l (represents d can divide l).(3)Corollary 1: If d|l, Eq. (3) is equivalent to(4)10Hongyu Zhao(赵宏宇 ) School of Inform. Sci. and Tech. 07/20/2009Proof: Modulo arithmetic(cont. 3)Corollary 2: If (a1,a2)=d and d|l, all the solutions of can be represented aswhere and satisfy(6)(5)