数论(一)概念与应用 刘汝佳.pptVIP

《算法艺术与信息学竞赛》标准课件 数论(一): 概念与应用 刘汝佳 目录 一、基本概念 二、进位制 三、模算术与方程 四、杂题 一、基本概念 概念1: 整除关系 整除与约数、倍数. 注意负数 可整除性的基本性质 若a|b, a|c, 则a|(b+c) 若a|b, 那么对所有整数c, a|bc 若a|b, b|c, 则a|c 整除关系具有传递性. 它是偏序关系(partial order), |,Z是一个格 概念2: 素数和合数 如果大于1的正整数p仅有的正因子是1和p, 则称p为素数(prime) 大于1又不是素数的正整数称为合数(compound) 如果n是合数, 则n必有一个小于或等于n1/2的素因子 定理1: 算术基本定理 每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的“乘积”可以有0个、1个或多个素因子）。 换句话说, 任意正整数n可以写成n=2a1*3a2*5a3*…,其中a1,a2,a3等为非负整数 这个定理也叫做惟一分解定理。它是一个定理而不是公理！虽然在大多人看来，它是“显然成立”的，但它的确是需要证明的定理 概念3: 除法和同余 令a为整数，d为正整数，那么有惟一的整数q和r，其中0≤rd，使得a=dq+r 可以用这个定理来定义除法：d叫除数，a叫被除数，q叫商，r叫余数。如果两个数a,b除以一个数c的余数相等，说a和b关于模c同余，记作a≡b(mod c) 概念4: 最大公约数和最小公倍数 令a和b是不全为0的两个整数，能使d|a和d|b的最大整数称为a和b的最大公约数，用gcd(a,b)表示，或者记为(a,b)。 令a和b是不全为0的两个整数，能使a|d和b|d的最小整数称为a和b的最小公倍数，用lcm(a,b)表示，或者记为[a,b] 想一想: 为什么不定义最小公约数和最大公倍数? 最大公约数的性质 GCD: Greatest Common Divisor 把a, b写成素数分解式 则(a,b)的公式为 最大公约数的性质 知道了最大公约数a, b，经常把a和b写为a=a1*(a,b), b=b1*(a,b)，则(a1,b1)=1，称a1和b1互素(relatively prime) GCD满足 分配律(ma,mb)=m(a,b) 结合律(a,b,c)=((a,b),c)=(a,(b,c)) 幂等律(a,a)=a 交换律(a,b)=(b,a) 吸收律[a,(a,b)]=a 最大公约数的性质 随机的两个整数互素的概率为 其中 为黎曼Zeta函数 [Polezzi, 1997](m,n)为从(0,0)到(m,n)的线段（不包含(m,n)）上格点的个数 [Knuth] 定理2: gcd(a,b)*lcm(a,b)=a*b 使用惟一分解定理. 设 则有: 容易验证定理成立 例题：除法表达式 除法表达式有如下的形式： X1 / X2 / X3 / … / Xk 其中Xi是正整数且Xi≤109 (k≤10,000)。 除法表达式应当按照从左到右的顺序求和，例如表达式1/2/1/2的值为1/4。可以在表达式中嵌入括号以改变计算顺序，例如表达式(1 / 2) / (1 / 2)的值为1。 现在给一个除法表达式E要求告诉是否可以通过增加括号使表达式值为整数。 分析 X2必须在分母, 其他都可以在分子 最后结果是整数吗？ 方法一: 把X2分解因数 方法二: 每次约掉X2和Xi的最大公约数 因数分解是困难的，因此方法二优 例题：无限赛跑 AB总长度为L 车一从A出发，速度为u 车二从B出发，速度为v 走到端点立刻返回，无时间损失 开车总时间t u, v, t都是正整数 相遇多少次？ 分析 第一种相遇: 相向t?(u+v)=(2k+1)L 第二种相遇: 同向t?|u?v|=(2k+1)L 重复: 在端点相遇 第一次同时到达端点时刻为r 到达不同端点? 到达同一端点 A和B分别运动2k1L和(2k2+1)L 下一次到达哪里? 不同端点?又同时到达此端点?同时到达另一端点? t=(2k+1)r 分析 如何求r? r是L/u的整数倍(u*r = k1L) r是L/v的整数倍 r是L/gcd(u,v)的整数倍 u/gcd(u,v) * r/(L/gcd(u,v)) = k1 r是满足条件的最小正数 r=L/gcd(u,v) 思考：反素数 正整数n是一个反素数，如果这个数的约数个数超过比n小的任何数的约数个数。 给定n(=2*109)，求不超过n的最大反素数数m 二、进位制 例题：集装箱 用若干个盒子（盒子的高度为2的非负整数次幂）填满若干个集装箱（高度也是2的非负整数次幂），所有盒子的价值和最小 盒子和集装箱的底面全等，因此只需要考虑高度 分析 对于每个尺寸的盒子，按照价