1、国际大学生程序设计竞赛数论与算法主讲：王树林数论基本知识 信息学中应用的关于素数和整除的知识并不多，关键在于灵活应用。 素数和整除问题 如果 a和 b是整数， a0，若有整数 c使 b ac，就说 a整除 b。在 a整除 b时，记 a是 b的一个因子， b是 a的倍数。用符号 ab表示 a整除 b， a不能整除b记为 a b。 整除基本性质有： （ 1）若 ab， ac，则 a（ b c） （ 2）若 ab，则对所有整数 c， abc （ 3）若 ab， bc，则 ac （传递性） 自反，反对称，传递性，偏序关系。 是一个格。 素数（ prime）和合数（ compound），如果一个整数 p
2、只有 1和 p两个因子，则 p为素数，不为素数的其它数为合数。如果 n为合数，则 n必有一个小于或等于 n的平方根的数因子。 算术基本定理：每个正整数都可以唯一地表示成素数的乘积。其中素数因子从小到大依次出现。数论基本知识 除法的定义和同余 a dq r。 同余： ab(mod c) 最大公约数 gcd(a,b) 最小公倍数 lcm(a,b) ab gcd(a,b)lcm(a,b) 如果 gcd(a,b)=1,则 a与 b互素。数论基本知识 1。如何求出 1 n中的所有素数？ Eraosthenes氏筛法：每次求出一个新的素数，就把 n以内的它的所有倍数都筛去。 2。给出一个数 n，如何判断它
3、是不是素数？ 1）朴素的判别法 从 2开始试除小于 n的所有自然数，时间复杂度为O(n). 2） 如果 a是 n的因子，那么 n/a也是 n的因子，所以如果 n有一个大于 1的真因子，则它必有一个不大于 n1/2的因子，时间复杂度 O(n1/2)。 等等。这些方法太慢。 伪素数：如果 n是一个正整数，并且存在和 n互素的正整数 a满足 an-1 1(mod n), 我们说 n是基于 a的伪素数。如果一个数是伪素数，它几乎肯定是素数。另一方面，如果一个数不是伪素数，它一定不是素数。数论基本知识 Miller-Rabbin测试function Miller-Rabbin(n:longint):bo
4、olean; begin for i:=1 to s do Begin a:=random(n-2)+2; If modular_exp(a,n-1,n)1 then return false; end; End; return true; End; 这是一个概率型算法，属于 Monte-Carlo算法系列。 时间复杂度为 O（ slog3n）。最大公约数的求法 欧几里德辗转相除法 function gcd(a,b:longint):longint; Begin if b=0 then gcd:=a; else gcd:=gcd(b, a mod b); End;扩展的欧几里德算法 如果（ a
5、， b） d，那么一定存在 x， y满足 ax by d。 Function extended_gcd(a,b:longint; Var x,y:longint):longint; Begin if b=0 then begin extended_gcd:=a; x:=1; y:=0; end else begin extended_gcd:=extended_gcd(b, a mod b); t:=x; x:=y; y:=t-(a div b) * y; end; End;佳佳的困惑 题目：给出一个数 N，含数字 1， 2， 3， 4，把 N的所有数字重新排列一下组成一个新数，使它是 7的倍
6、数。 分析：把数字 1， 2， 3， 4从中抽出，然后把其他数字按照原顺序排列组成的自然数 w， w10000整除 7取余有 7种可能，即是 0， 1， 2， 3， 4， 5， 6。如果能把 1， 2， 3， 4排列出 7个数，使它们整除 7取余的值分别为 0， 1， 2， 3， 4， 5， 6，把这 4位数接在 w后面即为问题的解。除法表达式 题目：除法表达式有如下的形式： X1/X2/X3/ Xk.其中 Xi是正整数且 X1000 000 000（ 1ik， k10 000）。除法表达式应当按照从左到右的顺序计算。可以在表达式中嵌入顺序。现在给一个除法表达式 E要求告诉是否可以通过增加括号使表达式为 E， E是整数。 分析： 显然 X1为分子， X2比为分母，其它数可以为分子也可以为分母。 方法一：将分母 X2分解质因数，由于X21000000000，所以质因数个数不超过 29个。逐一扫描 X1， X3， X4 ， Xk，看能否将X2约掉。 方法二：还是逐一扫描 X1， X3， X4 ， Xk，看能否将 X2约掉，但不进行因数分解，而是每次约掉它和 X2的最大公约数。
