您好,欢迎访问三七文档
长沙市雅礼中学朱全民数论知识点•素数与合数•质因素的分解•最大公约数与最小公倍数•整除与同余•同余方程与同余方程组•欧几里德算法、扩展欧几里德算法、中国剩余定理•欧拉定理与费马小定理思考题1:素数密度问题描述给定区间[L,R](L=R=2147483647,R-L=1000000),请计算区间中素数的个数。输入数据两个数L和R。输出数据一行,区间中素数的个数。梅森素数•把形如(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能够被分解为若干个不同的梅森素数之积。思考题2:fibonacci数列•已知f1=1,f2=1•fn=fn-1+fn-2•给出n,如何快速求fibonacci数列的fn分析Fn11Fn1Fn-110Fn2n-2Fn11F2Fn-110F1•普通的算法求Fn的时间复杂度为O(n),当然如果要求求出所有的Fn,这种已经是最优的了,但是如果只求某一个Fn,可以改进唯一因子分解唯一质因子分解定理:合数a仅能以一种方式,写成如下的乘积形式:a=p1e1p2e2…prer其中pi为素数,p1p2…pr,且ei为正整数关于约数的公式12121212221112222(1)(1)(1)1)1)1)rreeerreeerrrnpppneeenppppppppp若,则的因子个数为:所有因子的和为:(+(+(+n!的素因子分解式1212(,)118842,(,)202023571113171920reeerpnjjpnnpppnnppnp若!,则!其中=例如:求!的标准素因子分解式。!=问:!的十进位表示中有多少个零?整数分解方法•大整数分解现在任然是个世界级的难题!•而对于大整数的分解有很多种算法,性能上各有优异,比如大整数分解的Fermat方法,Pollardrho方法,试除法,以及椭圆曲线法,连分数法,二次筛选法,数域分析法等等。这里,主要讲解其中两种算法的原理和操作。费马分解法•首先,对于任意的一个偶数,我们都可以提取出一个2的质因子,如果结果仍为偶数,则可继续该操作,直至将其化为一个奇数和2的多少次幂的乘积,那么我们可以假定这个奇数可以被表示成2*N+1,如果这个数是合数,那么一定可以写成N=c*d的形式,不难发现,式中的c和d都是奇数,不妨设cd,我们可以令a=(c+d)/2,b=(c-d)/2,那么的可以得到N=a*a-b*b,而这正是Fermat整数分解的基础;由不等式的关系,我们又可以得到a=sqrt(c*d)=sqrt(N),那么,我们就可以枚举大于N的完全平方数a*a,计算a*a-N的值,判断计算的结果是否为一个完全平方数,如果是,那么a,b都是N的因子,我们就可以将算法递归的进行下去,知道求出N的所有质因子。Pollardrho算法•Pollardrho算法的原理就是通过某种方法得到两个整数a和b,而待分解的大整数为n,计算p=gcd(a-b,n),直到p不为1,或者a,b出现循环为止。然后再判断p是否为n,如果p=n成立,那么返回n是一个质数,否则返回p是n的一个因子,那么我们又可以递归的计算Pollard(p)和Pollard(n/p),这样,我们就可以求出n的所有质因子。•具体操作中,我们通常使用函数x2=x1*x1+c来计算逐步迭代计算a和b的值,实践中,通常取c为1,即b=a*a+1,在下一次计算中,将b的值赋给a,再次使用上式来计算新的b的值,当a,b出现循环时,即可退出进行判断。•在实际计算中,a和b的值最终肯定一出现一个循环,而将这些值用光滑的曲线连接起来的话,可以近似的看成是一个ρ型的。•对于Pollardrho,它可以在O(sqrt(p))的时间复杂度内找到n的一个小因子p,可见效率还是可以的,但是对于一个因子很少、因子值很大的大整数n来说,Pollardrho算法的效率仍然不是很好,那么,我们还得寻找更加的方法了。思考题3:除法表达式除法表达式有如下的形式:•X1/X2/X3/…/Xk•其中Xi是正整数且Xi≤109(1≤i≤k,k≤10000)。•除法表达式应当按照从左到右的顺序求和,–例如表达式1/2/1/2的值为1/4。•可以在表达式中嵌入括号以改变计算顺序,–例如表达式(1/2)/(1/2)的值为1。•现在给一个除法表达式E要求告诉是否可以通过增加括号使表达式值为E′,E′是整数。14同余•设m≠0,若m∣a-b,即a-b=km,则称a同余于b模m,记为•a、b关于模m同余的充要条件是整数a和b被同一正整数m除时,有相同的余数。)(modmba同余的性质同余的性质•若m≥1,(a,m)=1,则存在c使得ca≡1(modm)我们把c称为是a对模m的逆,记为a-1(modm)或a-1可以用扩展欧几里德算法求a-1例:求3406写成十进位数时的个位数.•根据题意是要求a满足3406≡a(mod10)显然32≡9≡-1(mod10),34≡1(mod10),从而3404≡1(mod10),因此3406≡3404×32≡9(mod10)所以个位数是9.思考题4:Hankson的趣味题(noip2009)•X和a0的最大公约数为a1•X和b0的最小公倍数为b1•给出a0,a1,b0,b1,求满足上述条件的x的个数?–根据整数模n所得的余数,可以把整数分成n个等价类:[0],[1],…,[n-1]。–包含整数的模n等价类为:[a]n={a+kn|k∈Z}模运算•有限群:–群(S,+)是一个集合S和定义在S上的二元运算+,它满足如下性质:1.封闭性:如果a,b∈S,那么a+b∈S。2.单位元:存在一个元素e,使得对于所有的a∈S都满足e+a=a+e=a。3.结合律:对于任意的a,b,c都满足(a+b)+c=a+(b+c)。4.逆元:对每个a∈S都存在唯一的元素b∈S使得a+b=b+a=e。把b称作a的逆元。21模运算•根据模加法和模乘法定义的群:–定义在集合Zn={0,1,2,……,n-1}上–集合上的加法和乘法运算定义为:•[a]n+n[b]n=[a+b]n•[a]n*n[b]n=[a*b]n思考题5:同余方程(NOIP2012)【问题描述】求关于x的同余方程ax≡1(modb)的最小正整数解。【输入】输入文件为mod.in。输入只有一行,包含两个正整数a,b,用一个空格隔开。【输出】输出文件为mod.out。输出只有一行,包含一个正整数x0,即最小正整数解。输入数据保证一定有解。【数据范围】对于40%的数据,2≤b≤1,000;对于60%的数据,2≤b≤50,000,000;对于100%的数据,2≤a,b≤2,000,000,000定理:方程ax=b(modn)对于未知量x有解,当且仅当gcd(a,n)|b。推论2:方程ax=b(modn)或者对模n有d个不同的解,其中d=gcd(a,n),或者无解。理论24Extended-Euclidean算法•对于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的解,那么对于a*x+b*y=d的解呢?25Extended-Euclidean算法b*x+(a%b)*y=d→b*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)Euclidean算法intgcd(inta,intb){intr;r=a%b;if(r==0)returnb;elsereturngcd(b,r);}该算法又叫辗转相除法Extended-Euclidean算法intexGcd(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returna;}intr=exGcd(b,a%b,x,y);intt=x;x=y;y=t-a/b*y;}相关定理•定理1:设d=gcd(a,n),假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d|b,则方程ax=b(modn)有一个解x0满足x0=x*(b/d)modn。特别的设e=x0+n,方程ax=b(modn)的最小整数解x1=emod(n/d),最大整数解x2=x1+(d-1)*(n/d)。•定理2:假设方程ax=b(modn)有解,且x0是方程的任意一个解,则该方程对模n恰有d个不同的解(d=gcd(a,n)),分别为:xi=x0+i*(n/d)modn。•两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。思考题6:青蛙的约会(POJ1061)•我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。•输入只包括一行5个整数x,y,m,n,L,其中x≠y2000000000,0m、n2000000000,0L2100000000。•输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行ImpossibleInput输入只包括一行5个整数x,y,m,n,L,其中x≠y2000000000,0m、n2000000000,0L2100000000。Output输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行Impossible“SampleInput12345SampleOutput4解题思路•此题其实就是扩展欧几里德算法-求解不定方程,线性同余方程。设过s步后两青蛙相遇,则必满足以下等式:(x+m*s)-(y+n*s)=k*l(k=0,1,2....)稍微变一下形得:(n-m)*s+k*l=x-y令n-m=a,k=b,x-y=c,即a*s+b*l=c•只要上式存在整数解,则两青蛙能相遇,否则不能。解题思路•求a*x+b*y=n的整数解。1、先计算Gcd(a,b),若n不能被Gcd(a,b)整除,则方程无整数解;否则,在方程两边同时除以Gcd(a,b),得到新的不定方程a'*x+b'*y=n',此时Gcd(a',b')=1;2、利用上面所说的欧几里德算法求出方程a'*x+b'*y=1的一组整数解x0,y0,则n'*x0,n'*y0是方程a'*x+b'*y=n'的一组整数解;3、根据数论中的相关定理,可得方程a'*x+b'*y=n'的所有整数解为:x=n'*x0+b'*ty=n'*y0-a'*t(t为整数)•上面的解也就是a*x+b*y=n的全部整数解。解题思路•此时方程的所有解为:x=c*k1-b*t。•x的最小的可能值是0–令x=0,可求出当x最小时的t的取值,但由于x=0是可能的最小取值,实际上可能x根
本文标题:noip数论知识
链接地址:https://www.777doc.com/doc-3995321 .html