刘汝佳-1数论初步.ppt

《刘汝佳-1数论初步.ppt》由会员分享，可在线阅读，更多相关《刘汝佳-1数论初步.ppt（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，其中0rd，使得a=dq+r 可以用这个定理来定义除法：d叫除数，a叫被除数，q叫商，r叫余数。如果两个数a,b除以一个数c的余数相等，说a和b关于模c同余，记作ab(mod c),同余,为什么有同余? 132412341+43

3、2435.2=24.7 余数可以作为原数的一个signature(标记). 如果标记下的运算错误, 一定错误 如果标记下的运算正确?,最大公约数和最小公倍数,令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 定理: ab = gcd(a,b) * lcm(a,b),定理的证明,使用惟一分解定理. 设 则有: 容易验证定理成立,例题：佳佳的困惑,给出一个数N，含数字1、2、3、4，把N的所有数字重新

4、排列一下组成一个新数，使它是7的倍数。,分析,把数字1、2、3、4从中抽出，然后把其他数字按照原顺序排列（事实上，怎么排列都无所谓）组成自然数w w*10,000整除7取余有7种可能，即是为0、1、2、3、4、5、6。这时如果能用数字1、2、3、4排列出7个数，使它们整除7取余的值分别为0、1、2、3、4、5、6，把这个4位数接在w后面即为问题的解。,例题：街道数,找所有的(n, k), 满足: 1+2+.+(n-1)=(n+1)+(n+2)+k 输出按k排序的前10个,分析,整理得: n(n-1)=(k-n)(n+k+1) 化简得: k2+k-2n2=0, 即n2=k(k+1)/2 由于k和

5、k+1互素, 因此 要么k是完全平方数 要么k/2是完全平方数 分别设k=m2和2m2, 枚举m,例题：齿轮,假设有三种齿轮：6齿，12齿，30齿。想要实现4 : 5的比例，一种可行方案如下： 给定可用的齿轮（每种均有无穷多），设计一系列传输c1 : d1, c2 : d2, , cm : dm，使得其综合比例(c1c2c3cm)/(d1d2d3dm)为给定值a:b。 给定齿轮的齿数为5到100，a和b不超过10000。,分析,使用惟一分解定理, 单独考虑各个素因子 c1 = p1a1*p2*a2* c2 = p1b1*p2*b2* 则c1x*c2y=p1(x*a1+y*b1) *p2(x*a

6、2+y*b2) 目标a:b = p1z1 * p2z2 x*a1+y*b1=z1; x*a2+y*b2=z2,分析,第i个齿轮的使用情况用xi表示，xi0表示用在分子xi次，xi0表示用在分母-xi次。 由于ai=100，只需要考虑100以内的25个素数 考虑每个素数pi的指数，可以构造一个线性方程，共25个等式 分子分母个数相等，故所有xi的和为0， 消元后枚举独立变量,例题：破解RSA,给定M个数，它们的质因子在前T个质数范围内。求这M个数组成集合的满足如下条件的非空子集个数：子集中所有数的积为完全平方数。,分析,首先将读入的M个数，分解质因数，并对每个质因数出现次数的奇偶性进行记录。 设

7、xi=0或1代表是否使用第i个数。可以列出一个关于xi(1=i=m)的位方程组（乘积的所有质因数出现次数均为偶数）。 解该方程组，检查最后有多少自变量，设有n个，那么结果应该是2n-1（除去空集）。 时空复杂度均为O(M2),思考：传球游戏,N个人围圈玩传球游戏，开始时第一个人拿着球，每个人把球传给左手的第K个人。满足1KN/2。求K的最大值，使得第一个人重新拿到球之前，每个人都拿过球。,基本问题,如何求1n的所有素数? 如何判断一个数n是否为素数? 如何求两个数的最大公约数? 如何给一个数n分解素因数?,问题1: 1n的素数,假设要求1100的素数 2是素数, 删除2*2, 2*3, 2*4

8、, , 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),思考：正多边形,给圆周上n个点的坐标, 能组成多少个正多边形？,问题2: 素数判定,枚举法: O(n1/2), 指数级别 改进的枚举法: O(phi(n1/2)=O(n1/2/logn), 仍然是指数级别 概率算法: Mille

9、r-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*1013以内唯一一个可以通过所有测试的数为3215031751,思考：区间内的素数,给出n, m(n=106, m=105), 求nn+m之间的素数有多少个 哪种方法快? 筛还是依次素数判定?,问题3: 最大公约数,方法一: 使用惟

10、一分解定理, 先分解素因数, 然后求最大公约数 方法二: (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) 如果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=

11、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 / 2) / (1 / 2)的值为1。 现在给一个除法表达式E要求告诉是否可以通过增加括号使表达式值为整数。,分析,X2必须在分母, 其他都可以在分子 最后结果是整数吗？ 方法一: 把X2分解因数 方法二: 每次约掉X2和Xi的最大

12、公约数 因数分解是困难的，因此方法二优,例题：无限赛跑,AB总长度为L 车一从A出发，速度为u 车二从B出发，速度为v 走到端点立刻返回，无时间损失 开车总时间t u, v, t都是正整数 相遇多少次？,分析,第一种相遇: 相向t(u+v)=(2k+1)L 第二种相遇: 同向t|uv|=(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/g

13、cd(u,v)的整数倍 u/gcd(u,v) * r/(L/gcd(u,v) = k1 r是满足条件的最小正数 r=L/gcd(u,v),问题4: 分解因数,分解因数可以转换为求最小素因子(找到最小素因子后递归求解) 分解素因数后得到惟一分解式sumpiki, 可以求出约数个数, 即所有ki+1的乘积(由乘法原理容易证明) 方法一: 试除法 方法二: pollard-rho算法,思考：反素数,正整数n是一个反素数，如果这个数的约数个数超过比n小的任何数的约数个数。 给定n(=2*109)，求不超过n的最大反素数数m,二、进位制,例题：集装箱,用若干个盒子（盒子的高度为2的非负次幂）填满若干个集

14、装箱（高度也是2的非负次幂），使所有盒子的价值和最小。 盒子和集装箱的底面全等，因此只需要考虑高度,分析,对于每个尺寸的盒子，按照价值从小到大排序 填充a的尺寸为0的集装箱时只能用尺寸为0的盒子，取最小的a个，剩下的两两组合供填充尺寸为1的集装箱时使用 当需要填充a个尺寸为k的集装箱时，选择尺寸为k的盒子中价值最小的a的，然后把剩下的两两组合成尺寸为k+1的供下一次选用 时间复杂度：O(n),例题：反转,TOM有9个寄存器a1.a9，支持以下操作 S i j, ajai+1 (i可能等于 j) P i, 输出ai 任务: 对于给定n=255，设计各个寄存器的初值和一个TOM程序，按顺序输出 n

15、, 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，每次准备好一个数后如果P限制还未达到，应该继续准备后面的数，而不要急着输出 对于n=255，P限制不大于4,算法二,基本思想：刚执行输出指令的寄存器马上改 考虑4个寄存器的情形，下划线是输出值 N, N-2, N-5, N-9

16、 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

17、，就缓解了压力 考虑这样的限制条件 任意两个相邻的2之间至少有一个0 从最低一位2向更低的位数找，也至少能找到一个0 限制条件避免了一次操作需要影响O(N)个二进制位的退化情况，类似于在排序二叉树中加入了“平衡因子”这个限制。因此不妨称这个限制条件为“平衡性质”。,分析,一开始的0序列满足平衡性质，因此需要构造从一个平衡状态到另一个平衡状态的过渡法则 对于增加2i，考察第i位： 0，那么0-1，考虑这个0所在的两个2之间的区间，如果剩下的都是1（没有0），那么把区间最左边的2进位 1，那么1-0，向前一位进1，如果前一位变成2，注意前一位的前面的区间是否全部都是1，如果那样也要和1)一样修改;

18、 如果前一位原来就是2，那么跳转3) 2，那么2-1，再将其前面一位加1即可,思考：天平,有一些砝码, 重量为1, 3, 9, 27, 81形如3k, 每个重量砝码只有一个. 任意给一个重量为m的物体, 把它放在天平左边, 如何把放置砝码使得天平平衡? 放在左边或者右边都可 m=10100,思考：987654321问题,求有多少个n位数平方以后的末9位为987654321。,思考：奇妙的数,给定n, m，寻找m位n进制数A，使得2A，3A，mA的数字均为A数字的排列 如m=6, n=10时，142,857是唯一解 给定数据最多只有一组解，也可能无解（如m=6, n=100时）,三、模算术与方程

19、,欧拉定理,欧拉函数: 1n中和n互素的元素个数(n) Euler定理 若gcd(a, n)=1则a(n) 1 (mod n) 意义：当b很大时ab ab mod (n)(mod n)，让指数一直比较小 欧拉函数是积性函数，即当(m,n)=1时f(mn)=f(m)*f(n),思考：欧拉函数的计算,给定n，需要多少时间计算(n)？ 给定n，需要多少时间计算(1), (2), , (n)的所有值？,例题：模取幂,a, p, m, n均为正整数，a, p为素数1a, p, m, n65535，且n2a, n2p。求： 如a=32719, p=54323, m=99, n=65399，则结果为4618

20、4,例题：模取幂,记f(a,p,m,n)为本题所求的数， n=1时，任何数模n都是0，所以f(a,p,m,n)=0，否则 a=1时，a的任何次幂都是1，结果为1 mod n；否则 m=0时，结果为=a mod n；否则 n=a时，a的次幂永远是n的倍数，结果为0；否则 n=2a时，因为a, p 2，如果a中有2的因子，则a的次幂永远是n的倍数，结果为0，否则为a；否则 a, n互素，f(a,p,m,n)=af(p,p,m-1,(n) mod n，问题转变成求ak mod n，可以二分求解,线性同余方程,axb(mod n) 方法一：利用Euler函数 a*a(n)-1 1 a(b*a(n)-1

21、) b 关键: 求abmod n a, a2, a4, a8, a16, 同余方程可以做乘法，b做二进制展开选择 方法二：扩展的Euclid算法 存在整数y，使得ax-ny=b 记d=(a,n)，a=a/d, n=n/d，必须有d|b ax-ny=1*(b/d) 注意：x不唯一, 所有x相差n/d的整数倍,中国剩余定理,考虑方程组xai(mod mi), mi两两互素 在0i时ei0(mod mj) 则e1a1+e2a2+ekak就是一个解, 调整得到0,m)内的唯一解（想一想，如何调整）,整理一下,一般线性方程组aixibi(mod ni) axb(mod n) xb1(mod n1) xb

22、1(mod n1) xb1(mod p1,i) 用中国剩余定理 其他规则同余方程 二项方程: 借助离散对数(本身?) 高次方程: 分解n, 降幂 单个多变元线性方程: 消法,例题：整数序列,已知A1,An、B、P求X1,Xn使得 A1X1+AnXn = B(mod P),分析,设g=(A1,A2,An,P)，若g不整除B则无解，否则我们可以用递归构造解： 将A1,An、P和B全部除以g，此时(A1,An),P)=1， 若n=1，则直接求X1使得A1X1 mod P=B；否则 设(A1,An-1)=D，则根据欧几里德算法一定存在x和y使得ANx + Dy = B(mod p)，可以令Xn=x ,

23、 则A1X1+An-1Xn-1=B-AnX=Dy(mod p),分析,(A1,An-1)=D, 所以(A1,An-1,P) = (D,P) | (Dy mod P), 因此完全转化为n-1的情形, 令B=DY mod P即可,四、杂题,例题：Fermat vs Pythagoras,给N(=100,000)，考虑满足x2+y2=z2(xyz=N)的三元组 求x、y、z互质的三元组的个数和不属于任何三元组(不光是互质)的k(k=N)的个数. 例(输入:输出) 10: 1 4 25: 4 9 100: 16 27,分析,本原三元组一定可以写成x=uv, y=u2-v2, z=u2+v2, 其中u,

24、 v互质 其他是本原三元组的整数倍 算法 预处理, 保存100,000内的所有本原三元组, 以z为关键字排序, di为z=i的个数, 递推 标记它们的倍数涉及到的数, 按序递推不属于任意三元组的个数gi 回答询问是O(1)的, 空间O(n),例题：没有矩形,n*n的网格, 要求每行每列恰好k个黑点，但任意四个黑点不构成矩形 输入k, 求n=k2-k+1的一个解 k=32且k-1为0, 1或素数,分析,每行用k个数表示黑色点的列编号, 则不存在矩形当且仅当任两行最多一个相同数 构造法. 第1行涂点1, 2, 3k 以下分k个块, 每块有k-1行, 共k2-k+1行 第i个块的一个点均为i 第一个

25、块的其他点为k+1k2-k+1 其他每个块的各行为第1个块的一个平移覆盖 以k=6为例, 第1行和第1个块(共6行)为:,1 2 3 4 5 6 1 7 8 9 10 11 1 12 13 14 15 16 1 17 18 19 20 21 1 22 23 24 25 26 1 27 28 29 30 31 以k=6为例 第一行为1k, 即16 每个块有k-1行, 即5行 第i个块的第一个数均为i 第1个块的其他点为k+1k2-k+1即731 下面开始一行一行构造第2个块,1 2 3 4 5 6 1 7 8 9 10 11 1 12 13 14 15 16 1 17 18 19 20 21 1

26、 22 23 24 25 26 1 27 28 29 30 31 2 7 14 21 23 30 第1个数总是2 第2从第1个块复制来一个7 以后每次从第1个块的下一行复制, 源的列号往右偏移2,1 2 3 4 5 6 1 7 8 9 10 11 1 12 13 14 15 16 1 17 18 19 20 21 1 22 23 24 25 26 1 27 28 29 30 31 2 7 14 21 23 30 2 8 15 17 24 31 第1个数还是2 这次从8开始复制 相当于选取的数是上一行右移了一个单位(比较黑色和兰色部分) 相当于用平移法构造k个链, 覆盖块1的其他数,1 2 3

27、4 5 6 1 7 8 9 10 11 1 12 13 14 15 16 1 17 18 19 20 21 1 22 23 24 25 26 1 27 28 29 30 31 2 7 14 21 23 30 2 8 15 17 24 31 2 9 16 18 25 27 2 10 12 19 26 28 2 11 13 20 22 29 3 7 15 18 26 29 第3块还是若干平移链, 但间隔变为3,1 2 3 4 5 6 1 7 8 9 10 11 1 12 13 14 15 16 1 17 18 19 20 21 1 22 23 24 25 26 1 27 28 29 30 31 2

28、 7 14 21 23 30 2 8 15 17 24 31 2 9 16 18 25 27 2 10 12 19 26 28 2 11 13 20 22 29 3 7 15 18 26 29 3 8 16 19 22 30,证明,先证合法性. 每行显然k个元素, 下面证明每列i也是k个元素 ik: i在第1个块中恰好出现过一次, 其他每块也恰好出现一次(每一块的各行是第一块的一个分解!)，因此一共恰好出现k次 下面证明没有矩形,证明,没有矩形当且仅当任意两行最多只有一个相同的数. 考虑每两行i, j, 规定ij 若i=1, j只有第1个数字出现在第一行 若i和j在同一个块内, 则只有第1个数相同 若i和j属于不同的两块, 则第1个数不同, 其他数来自两个间隔不同的链. 因为k-1是素数或0, 1, 所以此二链不可能有两个公共元素,