第8讲ACM数论问题.pptVIP

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为素数，不为素数的其它数为合数。如果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) 如果gcd(a, b)=1，则a与b互素。 素数算法 最一般的求解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( jsqrt(i) ) prime[num++] = i; } 素数 当n很大的时候，比如n=10,000,000时，n*sqrt(n)30,000,000,000,数量级相当大 思考如何改进？ 素数筛法 最简单的素数筛法 开一个大的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)内的素数求出来，用已经求得的素数来筛出后面的合数。 数论基本知识 如何求出1～n中的所有素数？ Eraosthenes（爱拉托斯尼筛法）筛法：每次求出一个新的素数，就把n以内的它的所有倍数都筛去。 伪素数 同余：a≡b(mod m) 如果两个数a和b之差能被m整除，那么我们就说a和b对模数m同余。比如，100-60除以8正好除尽，我们就说100和60对于模数8同余。它的另一层含义就是说，100和60除以8的余数相同。a和b对m同余，我们记作a≡b(mod m)。比如，刚才的例子可以写成100≡60(mod 8)。你会发现这种记号到处都在用，比如和数论相关的书中就经常把a mod 3 = 1写作a≡1(mod 3)。 伪素数 同余：a≡b(mod m) 如果两个数a和b之差能被m整除，那么我们就说a和b对模数m同余。比如，100-60除以8正好除尽，我们就说100和60对于模数8同余。它的另一层含义就是说，100和60除以8的余数相同。a和b对m同余，我们记作a≡b(mod m)。比如，刚才的例子可以写成100≡60(mod 8)。你会发现这种记号到处都在用，比如和数论相关的书中就经常把a mod 3 = 1写作a≡1(mod 3)。 伪素数：它满足费马小定理，但其本身却不是素数。最小的伪素数是341。事实上，费马小定理给出的是关于素数判定的必要非充分条件。若n能整除2^(n-1)-1，并n是非偶数的合数，那么n就是伪素数。第一个伪素数341 是萨鲁斯在1819年发现的。 费马尔小定理：若n是素数，且an且a0 则an-1≡1(mod n) 或 an-1 mod n =1 即 (an-1-1)/n=0 2^(5-1)-1=15,15|5. 2^(3-1)-1=3,3|3.但很多都是素数，如3，5，7，29，31…… 1819年数学家萨鲁斯找到了反例：2^(341-1)-1|341,而341=11*31是合数，341就成了第一个伪素数。以后又发现了许多伪素数：561 645 1105 1387 1729…… 伪素数 伪素数的一个用途 利用伪素数表来判定一个奇数n是否为素数。 如果n不能整除2^(n-1)－1，则据费马小定理知，n必为合数