acm入门第二讲数论

1、数论主要内容：筛法求素数欧几里德算法求最大公约数扩展欧几里德算法模线性方程的解法模线性方程组整除与约数对于整数d和a，如果存在整数k使得a=k*d，我们就说d能整除a ，记为d|a（读作d整除a）例如，因为24=3*8所以3能整除24，记为3|24如果d|a，并且d0，则称d是a的约数。例如，24的约数有1、2、3、4、6、8、12、24.每个整数a都可以被其平凡约数1和a整除，a的非平凡约数也称为a的因子。素数与合数对于某个大于1的整数a，如果它仅有平凡约数1和a则称a是素数（或质数）。否则称a是合数。素数有 2，3，5，7，11，13，17，19，23，29，素数有无穷多个素数的应用唯一素

2、因子分解定理：合数a仅能以一种方式，写成如下的乘积形式：a=p1e1p2e2prer 其中pi为素数，p1p2pr，且ei为正整数如果正整数n分解质因子的结果为n=p1e1p2e2prer， 则n的约数个数为: (e1+1)*(e2+1)*(er+1)。所有约数之和为：(1+p1+p12+p1e1)*(1+p2+p22+p2e2) *(1+pr+pr2+prer)素数的判定对于大于1的正整数a，如果a具有小于或等于sqrt（a）的素因子，则a为合数，否则a为素数。因此，可用区间2,sqrt(a)内的数去试除a，只要有一个数能整除a ，则a为合数，否则a为素数。这种判断素数的方法就是试除法。复杂

3、度O(sqrt(n).试除法IsPrime(a)for(i=2;i*isqrt(n)时筛中剩下的数就已经都是素数了。筛法求素数/用数组primeMAXN记录是否为素数；/primei为0表示i为素数，否则为合数int primeMAXN=0;for(i=2;i*i=n;i+)if(primei=0)for(j=i+i;j=n;j+=i)primej=1;因式分解tn=n;for(i=2;i*i1)/存在大于sqrt(n)的素因子p+cnt=tn;ecnt=1;例题一：Goldbachs Conjecture(TOJ1171)题目描述：对于输入的偶数n(6n1000000),是否可以表示为两个奇

4、素数之和。如果可以表示，输出表达式，否则输出Goldbachs conjecture is wrong. 例题一：Goldbachs Conjecture(TOJ1171)Sample Input8 20 42 0 Sample Output8 = 3 + 5 20 = 3 + 17 42 = 5 + 37 例题一：Goldbachs Conjecture(TOJ1171)假设两个奇素数中较小的一个为a， 让a从2取到n/2，如果a取到某个值时a与n-a都为素数，则此时的a与n-a的值便是所求。如果最终找不到满足条件的a则无解，输出“Goldbachs conjecture is wrong.

5、”即可。 因此可以用筛法预先计算出21000000内的素数，然后判断即可最大公约数与最小公倍数d是a的约数并且也是b的约数，则d是a与b的公约数。两个不同时为0的整数a和b的最大公约数表示为gcd(a, b)。如果d既能被a整除也能被b整除，则d是a与b的公倍数，a与b公倍数中最小的叫a与b的最小公倍数，表示为lcm(a,b).gcd(a,b)*lcm(a,b)=a*b最大公约数为1的两个数互质最大公约数的求法GCD递归定理：对任意非负整数a和任意正整数b，有gcd(a, b) = gcd(b, a mod b) 。最大公约数的求法欧几里德算法（也叫辗转相除法）：EUCLID(a, b)if

6、b = 0then return aelse return EUCLID(b, a % b)例如:gcd(18,24)=gcd(24,18)=gcd(18,6)=gcd(6,0)=6算法复杂度O(lg(b)欧几里德算法int gcd(int a,int b)if(b=0)return a;return gcd(b,a%b);扩展欧几里德算法通过欧几里德算法我们不仅能求出a与b的最大公约数，还可以改写欧几里德算法，求出整数x和y 使得gcd(a,b)=ax+by扩展欧几里德算法设a=a mod b= a-b*floor(a/b);假如我们通过递归得到了gcd(b,a)=b*x+a*y的x,y的值

7、，则因为gcd(a,b)=gcd(b,a mod b )=gcd(b,a);有等式gcd(a,b)=b*x+a*y代入a可以得到gcd(a,b)=b*x+(a-b*floor(a/b)*y即gcd(a,b)=a*y+b*(x-floor(a/b)*y)所以只要将gcd(a,b)=a*x+b*y中的x换为y,y换为x-floor(a/b)*y即可，同时我们有递归的基本情形gcd(a,0)=a*1+b*0.扩展欧几里德算法1. EXTENDED-EUCLID(a, b)2.if b = 03.then return (a, 1, 0)4.(d,x,y) EXTENDED-EUCLID(b, a%b

8、)5.(d, x, y) (d, y, x(a/b) * y)6.return (d, x, y)扩展欧几里德算法int ext_gcd(int a,int b,int &x,int &y)if(b=0)x=1;y=0;return a;int d=ext_gcd(b,a%b,x,y);int tx=x;x=y;y=tx-a/b*y;return d;例题二：A famous math puzzle (TOJ2219)题目描述：有n个壶，和无穷多的水每次我们只能：把其中一个壶灌满把其中一个壶倒空把一个壶中的水倒入另一个壶中，直到一个壶为空或者另一个壶已经满了为止给定一个体积，问能否经过若干次倒

9、水后使得最终有一个壶中只剩下升水？如果能，输出”YES”,否则输出”NO”例题二：A famous math puzzle (TOJ2219)Sample Input:2 4 5 62 10 65 39 2 12 4 8 3 9 10 35 14 0 0 Sample Output:YESNONOYES 例题二：A famous math puzzle (TOJ2219)要使n个水壶能倒出w体积的水，则必须符合以下两个条件：至少有一个水壶的容量大于或等于w.假设p是n个水壶容量的最大公约数，那么w必须p的倍数例题二：A famous math puzzle (TOJ2219)假设n个水壶的容量

10、分别为C1,C2,C3 .必要性：不管执行三种操作的那一种，壶中所含的水一定是的整数倍充分性：由欧几里德算法扩展可知，必然存在整数A1,A2,A3.An,使得A1*C1+A2*C2+A3*C3+An*Cn=W. 如果Ai是正数，我们就用第i个壶从水源中取Ai次水；如果Ai为负数，我们就把第i个壶倒空Ai次，这样最后必会剩下升水同余的概念两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余记作 a b (mod m) 读作a与b关于模m同余。 模的相关运算(x+y)mod n=(x mod n)+(y mod n) mod n(x-y)mod n=(x mod n) - (y

11、mod n) mod nx*y mod n = (x mod n)*(y mod n) mod n乘法逆元若ax1(mod n) 则称a对n的乘法逆元为x ,记为a-1(mod n)设b为整数，如果a对n的乘法逆元为x ，则b/a(mod n) =b*a-1 (mod n)乘法逆元并不总存在，如2x 1(mod 4).模线性方程axb(mod n)为模线性方程，x为未知数。定理一：设d=gcd(a, n)，假定对整数x和y，有d=ax+ny。如果d|b，则方程ax b(mod n)有一个解的值为x0，满足x0=x(b/d)mod n。定理二：假设方程ax b(mod n)有解（即有d|b，其中

12、d=gcd(a, n)），x0是该方程的任意一个解，则该方程对模n恰有d个不同的解，分别为：xi=x0+i(n/d)(i = 1, 2, , d-1)。模线性方程的解法1. SOLVE(a, b, n)2. (d,x,y) EXTENDED-EUCLID(a, n)3. if (d | b)4. then x0 x(b/d)mod n5. for i 0 to d-16. print(x0 + i(n / d) mod n7.else print “无解”例题三：C Looooops (TOJ 2297)题意描述：对于以下循环语句for (variable = A; variable != B

13、; variable+= C) statement;如果给定A，B，C，k的值，statement语句会执行多少次，假设其中所有变量都是k位无符号整数类型，（1 k 32 ）如果此循环语句不会停止，输出” FOREVER”，否则输出执行次数。输入数据以4个0结束例题三：C Looooops (TOJ 2297)Sample Input3 3 2 16 3 7 2 16 7 3 2 16 3 4 2 16 0 0 0 0 Sample Output0 2 32766 FOREVER 例题三：C Looooops (TOJ 2297)因为所有变量都是k位无符号整数类型，当语句执行X次后，变量var

14、iable 的值变为(A+C*X)(mod 2k)所以当(A+C*X)(mod 2k)=B(mod 2k)时循环停止，化简得C*X(B-A)(mod 2k),解模线性方程求出所有X，如果有解，输出最小的正整数解即可，否则输出“FOREVER”。模线性方程组例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？答曰：二十三。232*70+3*21+2*15(mod 105)口诀：三人同行七十稀，五树梅花廿一枝， 七子团圆月正半，除百零五便得知。模线性方程组中国剩余定理：设自然数n1,n2,nr两两互素，并记N=n1n2nr，则同余方程组在模N同余的意义下有唯一解。X(a1c1+a2c2+arcr)(mod N)其中，ci=mi*(mi-1mod ni),mi=N/ni因为 Xmod ni=(a1m1m1-1+a2m2m2-1+armrmr-1) mod ni=(aimimi-1 )mod ni=aimod ni中国剩余定理/ 计算 X mod ni = ai (i = 1.k)int China(int k, int a, int n) ans = 0; N = 1 for(i = 0; i k