1、1,ACM 数论,http:/10.7.18.82/vjudge/contest/contest/view.action?cid=6#overview,2,初等数论的概念,整除性和约数：假设d和a是整数，d|a（读作d整除a），意味着存在某个整数k，有a=kd。如果d|a，并且d0，则称d是a的约数。每个整数a都可以被其平凡约数1和a整除，a的非平凡约数也称为a的因子。,3,初等数论的概念,素数和合数对于某个整数a1，如果它仅有平凡约数1和a则称p是素数。否则p是合数。可以证明素数有无限多个。筛法求素数。,4,求素数方法,1）pN存储所有的素数，二重循环，用已经求出的不大于平方根的所有素数试除
2、for(i=2;in;+i)for(j=0;jm (m+),5,2）给定一个范围（求这个范围内的素数），进行如下步骤： 0.从2开始，2是第一个素数。也是第一个新素数。取出2。 1.筛掉所有新素数的倍数。 2.留下来的数里面第一个（最小的）是新素数。取出这个新素数。 3.重复1和2直到没有数存在。,Eratosthenes筛法,6,O(n)筛素数,void Init() int i,j,q,n,cnt=0; memset(mark,0,sizeof(mark); n=1000; for(i=2;in)break; markprimej*i=primej;if(marki=primej)/pri
3、ntf(%d %d mark=%dn,i,j,marki);break; 内网B、C题,7,初等数论概念,除法定理，余数除法定理：对任意整数a和任意正整数n，存在唯一的整数q和r，使得a=qn+r，其中0rn。值q成为除法的商，值r=a(mod n)称为除法的余数。,8,初等数论的概念,公约数与最大公约数d是a的约数并且也是b的约数，则d是a和b的公约数。两个不同时为0的整数a和b的最大公约数表示为gcd(a, b)。,9,初等数论的概念,gcd(a, b) 的性质：定理：如果a，b是不全为0的任意整数，则gcd(a, b)是a与b的线性组合ax+by:x,yZ中的最小正元素。推论1：对于任意
4、整数a，b，如果d|a并且d|b，则d|gcd(a, b)。推论2：对于所有整数a和b以及任意非负整数n，gcd(an, bn)=n*gcd(a,b)。推论3：对所有正整数n，a和b，如果n|ab并且gcd(a, n)=1，则n|b。,10,初等数论的概念,互质数：如果两个整数a与b只有公因数1，即如果gcd(a, b)=1，则a与b称为互质数（互素）。定理：对任意整数a，b和p，如果gcd(a, p)=1且gcd(b, p)=1，则gcd(ab, p) = 1。,11,最大公约数 gcd（最大公因子）,Euclidean算法求两个正整数a和b的gcd。先令r0为a，r1为b，接着执行如下运算
5、：,12,最大公约数,GCD递归定理：对任意非负整数a和任意正整数b，gcd(a, b) = gcd(b, a mod b)。,13,欧几里德算法：EUCLID(a, b) if b = 0 than return a else return EUCLID(b, a % b),14,二进制最大公约数算法：如果a和b都是都是偶数，那么gcd(a, b) = 2gcd(a/2, b/2)。如果a是奇数，b是偶数，那么gcd(a, b) = gcd(a, b/2)。如果a和b都是奇数，那么gcd(a, b) = (ab)/2, b)。吉林大学模板,15,思考： 将两个整数的欧几里德算法推广到求m个整
6、数的最大公约数。（两种方法）,16,Extended-Euclidean 算法,定理：对于不完全为0的非负整数a，b，gcd（a，b）表示a，b的最大公约数d，必然存在整数对x，y，使得gcd（a，b）=d=ax+by。,17,扩展欧几里德算法,对于gcd(a,b) = d，对(a, b)用欧几里德辗转相除会最终得到(d, 0)。此时对于把a =d, b = 0 代入a*x + b*y = d，显然x = 1，y可以为任意值。我们可以用a = d, b = 0的情况逆推出来任何gcd(a, b) = d 满足a*x + b*y = d的解。如果x0，y0是b*x + (a%b)*y = d 的
7、解，那么对于a*x + b*y = d的解呢？,18,扩展欧几里德算法,b*x + (a%b)*y = db*x + (a - a/b*b)*y = a*y + b*(x - a/b*y)，所以a*x + b*y = d的解x1 = y0， y1= x0 - a/b*y0; 这样我们可以程序迭代了。,注：a,b为正整数，设集合A = x*a+y*b|x,y是整数，则A中最小正元素是gcd(a,b),19,扩展欧几里德算法：EXTENDED-EUCLID(a, b) if b = 0 then return (a, 1, 0) (d,x,y) EXTENDED-EUCLID(b, a%b) (d
8、, x, y) (d, y, x (a/b) * y) return (d, x, y),20,扩展欧几里德算法,21,例如：a4864，b3458，则由上述算法可得gcd（4864，3458）38，且（4864）（38）（3458）（45）38,22,LCM(Least Common Multiple),有了 GCD, LCM 就好办了LCM ( a, b ) = a * b / GCD ( a, b ) 实际上最好写成a/GCD(a,b)*b思考：为什么下面的写法好？,23,初等数论概念,唯一因子分解唯一质因子分解定理：合数a仅能以一种方式，写成如下的乘积形式：a=p1e1p2e2prer
9、其中pi为素数，p1p2pr，且ei为正整数。,24,其他一些关于约数的公式,25,n！的素因子分解式,26,反素数,问题描述:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0ix),都有g(i)求约数最多的数如果求约数的个数 756=22*33*71(2+1)*(3+1)*(1+1)=24基于上述结论,给出算法:按照质因数大小递增顺序搜索每一个质因子,枚举每一个质因子为了剪枝:性质一:一个反素数的质因子必然是从2开始连续的质数.因为最多只需要10个素数构造:2,3,5,7,11,13,17,19,23,29性质二:p=2t1*3
10、t2*5t3*7t4.必然t1=t2=t3=.内网F题,28,同余,设m0，若mab，即abkm，则称a同余于b模m，记为a、b关于模m同余的充要条件是整数a和b被同一正整数m除时，有相同的余数。,29,同余的性质,30,同余的性质,若m1，（a，m）1，则存在c使得 ca1（mod m）我们把c称为是a对模m的逆，记为 a1（mod m）或a1可以用扩展欧几里德算法求a1应用：(a/b)%m-(a%m)/(b%m)？省赛,31,例：求3406写成十进位数时的个位数.,根据题意是要求a满足3406 a（mod 10）显然32 9 1 （mod 10），34 1 （mod 10），从而3404
11、1 （mod 10），因此3406 3404 32 9（mod 10）所以个位数是9.,32,根据整数模n所得的余数，可以把整数分成n个等价类：0,1,n-1。包含整数的模n等价类为：an=a+kn| kZ,33,求解模线性方程,定理：方程ax=b(mod n)对于未知量x有解，当且仅当gcd(a, n)|b定理：方程ax=b(mod n)或者对模n有d个不同的解，其中d=gcd(a, n)或者无解。,34,求解模线性方程,定理：设d=gcd(a, n)，假定对整数x和y，有d=ax+ny。如果d|b，则方程ax=b(modn)有一个解的值为x0，满足x0=x(b/d)mod n。,35,求解
12、模线性方程,定理：假设方程ax=b(mod n)有解（即有d|b，其中d=gcd(a, n)），x0是该方程的任意一个解，则该方程对模n恰有d个不同的解，分别为：xi=x0+i(n/d)(i = 1, 2, , d-1)。,36,求解模线性方程,MODULAR-LINEAR_EQUATION_SOLVER(a, b, n) (d,x,y) EXTENDED-EUCLID(a, n) if (d | b) then x0 x(b/d)mod n for i 0 to d-1 do print(x0 + i(n / d) mod n else print “no solution”,37,模线性方
13、程,定理：对任意n1，如果gcd(a, n)=1，则方程ax=b(mod n)对模n有唯一解。定理：对任意n1，如果gcd(a, n)=1，则方程ax=1(mod n)对模n有唯一解，否则无解。,38,公元56世纪前后的孙子算经中有“物不知数”问题：“今有物不知其数，三三数之余二 ，五五数之余三 ，七七数之余二，问物几何？”答为“23”。也就是求同余式组x2 （mod3），x3 （mod5 ），x2 （mod7）的正整数解。明朝程大位用歌谣给出了该题的解法：“三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。”即解为 x27032121523323(mod105）。,中国剩余定理
14、,39,中国剩余定理（孙子定理）,40,问题：给定两两互质的正整数n1,n2,.,nk，要求找到最小的正整数a，满足aai (mod ni)算法步骤:令n=n1n2.nk，mi=n/ni显然gcd(mi,ni)=1，解模线性方程，计算出xi满足mixi1 (mod ni)aa1x1m1+a2x2m2+.+akxkmk (mod n),41,欧拉函数,Euler函数 ：设m是正整数，1，2，m中与m互素的数的个数。定理：,42,欧拉定理的推广形式当x (m)时，AxA(x mod (m)+ (m) (mod m),43,定理：如果p是一个奇素数且e1，则方程x2=1(mod pe)仅有两个解：x
15、=1和x=-1。定理：如果对模n存在1的非平凡平方根，则n是和数。,44,元素的幂,3k mod 7为：i 0 1 2 3 4 5 6 7 8 9 10 113k mod 7 1 3 2 6 4 5 1 3 2 6 4 52k mod 7为：i 0 1 2 3 4 5 6 7 8 9 10 112k mod 7 1 2 4 1 2 4 1 2 4 1 2 4,45,素数测试,46,素数测试,47,素数测试,48,素数测试,要判断一个整数n是不是素数，应用费马定理：如果n是素数，那么对于任意的a都满足an-1=1(mod n)。所以可以通过随机选取若干个a，来检验n是否是素数。,49,素数测试,
16、如果n是合数，并且满足an-1=1(mod n)那么就说n是一个基为a的伪素数。,50,素数测试,然而，并不能通过增加随机次数来增加这种测试的正确性，因为存在一些合数，也满足对于任意的a，an-1=1(mod n)通常把这样的合数称为Carmichael数。前三个Carmichael数是561，1105和1729。Carmichael数是非常少的，在小于100000000的数中，只有255个Carmichael数。,51,大数的素性检测,Rabin-Miller素数测试非素数通过测试概率为 Pollard-算法大数的快速分解,52,53,54,梅森素数,把形如(2p-1)形式的素数称为梅森素数，p是素数。1, 231-1之间的梅森素数有：22-1, 23-1, 25-1, 27-1, 213-1, 217-1, 219-1, 231-1梅森素数的一个性质：一个正整数n的所有约数和是2的幂当且仅当n能够被分解为若干个不同的梅森素数之积。,55,56,THANK YOU！,
