《ACM数论问题》PPT课件.ppt

《《ACM数论问题》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM数论问题数论基本知识信息学竞赛和程序设计竞赛中常考的数论知识关于素数和整除，关键在于灵活应用整除:如果a和b是整数，a≠0，若有整数c使b＝ac，就说a整除b。在a整除b时，记a是b的一个因子，b是a的倍数。用符号a∣b表示a整除b，a不能整除b记为a⊥b。整除基本性质有：（1）若a∣b，a∣c，则a∣（b＋c）（2）若a∣b，则对所有整数c，a∣bc（3）若a∣b，b∣c，则a∣c（传递性）数论基本知识素数（prime）和合数（compound），如果一个整数p只有1和p两个因子，则p为素

2、数，不为素数的其它数为合数。如果n为合数，则n必有一个小于或等于n的平方根的数因子。给出一个数n，如何判断它是不是素数？朴素的判别法从2开始试除小于n的所有自然数，时间复杂度为O(n).如果a是n的因子，那么n/a也是n的因子，所以如果n有一个大于1的真因子，则它必有一个不大于n1/2的因子，时间复杂度O(n1/2)。算术基本定理：每个正整数都可以唯一地表示成素数的乘积。其中素数因子从小到大依次出现。最大公约数gcd(a,b)最小公倍数lcm(a,b)ab＝gcd(a,b)×lcm(a,b)如果g

3、cd(a,b)=1，则a与b互素。工大ACM团队素数算法最一般的求解n以内素数的算法。复杂度是o(n*sqrt(n))，适合n很小num=0;for(i=2;i<=n;i++){for(j=2;j<=sqrt(i);j++)if(i%j==0)break;if(j>sqrt(i))prime[num++]=i;}工大ACM团队素数当n很大的时候，比如n=10,000,000时，n*sqrt(n)>30,000,000,000,数量级相当大思考如何改进？工大ACM团队素数筛法最简单的素数筛法开一个大

4、的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false.把奇数的倍数设为false.见代码-prime_choice.c改进的素数筛法bool型数组里面只存奇数不存偶数。如定义prime[N],则0表示3，1表示5，2表示7，3表示9...。如果prime[0]为true,则表示3时素数。prime[3]为false意味着9是合数，每个单元代表的数是2*i+3。欲求n以内的素数，就先把sqrt(n)内的素数求出来，用已经求得的素数来筛

5、出后面的合数。工大ACM团队数论基本知识如何求出1～n中的所有素数？Eraosthenes（爱拉托斯尼筛法）筛法：每次求出一个新的素数，就把n以内的它的所有倍数都筛去。经典的Eraosthenes筛法：for(inti=2;i*i

6、度是O(n)）：voidget_prime(){intcnt=0;    for(inti=2;i

7、都唯一的被它的最小素因子筛一次，而每个合数的最小素因子都是唯一的，总复杂度是O(n)Eraosthenes筛法的速度并不快，原因在于对于一个合数，这种方法会重复的标记工大ACM团队伪素数同余：a≡b(modm)如果两个数a和b之差能被m整除，那么我们就说a和b对模数m同余。比如，100-60除以8正好除尽，我们就说100和60对于模数8同余。它的另一层含义就是说，100和60除以8的余数相同。a和b对m同余，我们记作a≡b(modm)。比如，刚才的例子可以写成100≡60(mod8)。你会发现这种

8、记号到处都在用，比如和数论相关的书中就经常把amod3=1写作a≡1(mod3)。工大ACM团队伪素数同余：a≡b(modm)如果两个数a和b之差能被m整除，那么我们就说a和b对模数m同余。比如，100-60除以8正好除尽，我们就说100和60对于模数8同余。它的另一层含义就是说，100和60除以8的余数相同。a和b对m同余，我们记作a≡b(modm)。比如，刚才的例子可以写成100≡60(mod8)。你会发现这种记号到处都在用，比如和数论相关的书中就经常把amod3=1写作a≡1