刘汝佳-1数论初步

《刘汝佳-1数论初步》由会员分享，可在线阅读，更多相关《刘汝佳-1数论初步（72页珍藏版）》请在金锄头文库上搜索。

1、2005年浙江省队培训 第1讲 数论初步,刘汝佳,目录,一、基本概念 二、进位制 三、模算术与方程 四、杂题,一、基本概念,基本概念,整除与约数、倍数. 注意负数 可整除性的基本性质 若a|b, a|c, 则a|(b+c) 若a|b, 那么对所有整数c, a|bc 若a|b, b|c, 则a|c 整除关系具有传递性. 它是偏序关系(partial order), 是一个格,素数和合数,如果大于1的正整数p仅有的正因子是1和p, 则称p为素数(prime) 大于1又不是素数的正整数称为合数(compound) 如果n是合数, 则n必有一个小于或等于n1/2的素因子,算术基本定理,每个正整数都可以

2、惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的“乘积”可以有0个、1个或多个素因子）。 换句话说, 任意正整数n可以写成n=2a1*3a2*5a3*,其中a1,a2,a3等为非负整数 这个定理也叫做惟一分解定理。它是一个定理而不是公理！虽然在大多人看来，它是“显然成立”的，但它的确是需要证明的定理,除法和同余,令a为整数，d为正整数，那么有惟一的整数q和r，其中0r0表示用在分子xi次，xi0表示用在分母-xi次。 由于ai=100，只需要考虑100以内的25个素数 考虑每个素数pi的指数，可以构造一个线性方程，共25个等式 分子分母个数相等，故所有xi的和为0， 消元后枚举独立

3、变量,例题：破解RSA,给定M个数，它们的质因子在前T个质数范围内。求这M个数组成集合的满足如下条件的非空子集个数：子集中所有数的积为完全平方数。,分析,首先将读入的M个数，分解质因数，并对每个质因数出现次数的奇偶性进行记录。 设xi=0或1代表是否使用第i个数。可以列出一个关于xi(1=i=m)的位方程组（乘积的所有质因数出现次数均为偶数）。 解该方程组，检查最后有多少自变量，设有n个，那么结果应该是2n-1（除去空集）。 时空复杂度均为O(M2),思考：传球游戏,N个人围圈玩传球游戏，开始时第一个人拿着球，每个人把球传给左手的第K个人。满足1KN/2。求K的最大值，使得第一个人重新拿到球之

4、前，每个人都拿过球。,基本问题,如何求1n的所有素数? 如何判断一个数n是否为素数? 如何求两个数的最大公约数? 如何给一个数n分解素因数?,问题1: 1n的素数,假设要求1100的素数 2是素数, 删除2*2, 2*3, 2*4, , 2*50 第一个没被删除的是3, 删除3*3, 3*4, 3*5,3*33 第一个没被删除的是5, 删除5*5, 5*6, 5*20 得到素数p时, 需要删除p*p, p*(p+1), p*n/p, 运算量为n/p-p, 其中p不超过n1/2(想一想, 为什么),Eratosthenes的筛子,小知识 (),近似公式(Legendre常数B=-1.08366)

5、,思考：正多边形,给圆周上n个点的坐标, 能组成多少个正多边形？,问题2: 素数判定,枚举法: O(n1/2), 指数级别 改进的枚举法: O(phi(n1/2)=O(n1/2/logn), 仍然是指数级别 概率算法: Miller-Rabin测试 + Lucas-Lehmer测试,Miller-Rabin测试,对于奇数n, 记n=2r*s+1, 其中s为奇数 随机选a(1=a=n-1), n通过测试的条件是 as1(mod n), 或者 存在0=j=r-1使得a2j*s-1(mod n) 素数对于所有a通过测试, 合数通过测试的概率不超过1/4 只测试a=2, 3, 5, 7, 则2.5*1

6、013以内唯一一个可以通过所有测试的数为3215031751,思考：区间内的素数,给出n, m(n=106, m=105), 求nn+m之间的素数有多少个 哪种方法快? 筛还是依次素数判定?,问题3: 最大公约数,方法一: 使用惟一分解定理, 先分解素因数, 然后求最大公约数 方法二: (Euclid算法)利用公式gcd(a, b)=gcd(b, a mod b), 时间复杂度为O(logb) 方法三: (二进制算法) 若a=b, gcd(a,b)=a, 否则 A和b均为偶数, gcd(a,b)=2*gcd(a/2,b/2) A为偶数, b为奇数, gcd(a,b)=gcd(a/2,b) 如果

7、a和b均为奇数, gcd(a,b)=gcd(a-b,b) 不需要除法, 适合大整数,扩展问题,一定存在整数x,y，使得ax+by=gcd(a,b) int gcd(int a, int b, int 由数学归纳法可证明ax+by=gcd(a,b) 满足ax+by=d的数对(x,y)不是惟一的, 因为当x增加b且y减少a时和不变。,例题：除法表达式,除法表达式有如下的形式： X1 / X2 / X3 / / Xk 其中Xi是正整数且Xi109 (k10,000)。 除法表达式应当按照从左到右的顺序求和，例如表达式1/2/1/2的值为1/4。可以在表达式中嵌入括号以改变计算顺序，例如表达式(1 /

8、 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|uv|=(2k+1)L 重复: 在端点相遇 第一次同时到达端点时刻为r 到达不同端点? 到

9、达同一端点 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),问题4: 分解因数,分解因数可以转换为求最小素因子(找到最小素因子后递归求解) 分解素因数后得到惟一分解式sumpiki, 可以求出约数个数, 即所有ki+1的乘积(由乘法原理容易证明) 方法一: 试除法 方法二: pollard-

10、rho算法,思考：反素数,正整数n是一个反素数，如果这个数的约数个数超过比n小的任何数的约数个数。 给定n(=2*109)，求不超过n的最大反素数数m,二、进位制,例题：集装箱,用若干个盒子（盒子的高度为2的非负次幂）填满若干个集装箱（高度也是2的非负次幂），使所有盒子的价值和最小。 盒子和集装箱的底面全等，因此只需要考虑高度,分析,对于每个尺寸的盒子，按照价值从小到大排序 填充a的尺寸为0的集装箱时只能用尺寸为0的盒子，取最小的a个，剩下的两两组合供填充尺寸为1的集装箱时使用 当需要填充a个尺寸为k的集装箱时，选择尺寸为k的盒子中价值最小的a的，然后把剩下的两两组合成尺寸为k+1的供下一次选

11、用 时间复杂度：O(n),例题：反转,TOM有9个寄存器a1a9，支持以下操作 S i j, ajai+1 (i可能等于 j) P i, 输出ai 任务: 对于给定n=255，设计各个寄存器的初值和一个TOM程序，按顺序输出 n, n-1, n-2, 0 最长的“连续S操作”片段长度P应尽量小,算法一,寄存器i(i=8)负责输出最右的非零位为第i位的数 初始时设置每个寄存器为此类数的最大值，寄存器1-8依次为128, 192, 224, 240, 248, 252, 254, 255，寄存器9保持0 输出248(11111000)后，应准备232(11101000) 设置连续S操作个数的限制P

12、，每次准备好一个数后如果P限制还未达到，应该继续准备后面的数，而不要急着输出 对于n=255，P限制不大于4,算法二,基本思想：刚执行输出指令的寄存器马上改 考虑4个寄存器的情形，下划线是输出值 N, N-2, N-5, N-9 N-1, N-2, N-5, N-9 N-4, N-2, N-5, N-9 N-4, N-3, N-5, N-9 N-4, N-8, N-5, N-9 N-7, N-8, N-5, N-9 N-7, N-8, N-6, N-9 推广到9的寄存器，对于N=44，可得到P=1的解,例题：奇怪的计数器,用如下方式表示数： AN-1*2N-1+AN-2*2N-2+ . +A12+A0 每个A在范围02内。 初始时所有的A均为0，要处理M次加2x的操作（每个x不一定都相同），每次最多只允许修改4个A的内容。 要求模拟这一过程。,分析,多个2连在一起比较“危险”，容易超过4次的限额 让它们之间存在一个0，就缓解了压力 考虑这样的限制条件 任意两个相邻的2之间至少有一个0 从最低一位2向更低的位数找，也至少能找到一个0 限制条件避免了一次操作需要影响O(N)个二进制位的退化情况，类似于在排序二叉树中加入了“平衡因子”这个限制。因此不妨称这个限制条件为“平衡性质”。,