1_数论初步

刘汝佳 黑书 课件 经典

2005年浙江省队培训 第1讲 数论初步刘汝佳

刘汝佳 黑书 课件 经典

目录一、基本概念 二、进位制 三、模算术与方程 四、杂题

刘汝佳 黑书 课件 经典

一、基本概念

刘汝佳 黑书 课件 经典

基本概念 整除与约数、倍数. 注意负数 可整除性的基本性质– 若a|b, a|c, 则a|(b+c) – 若a|b, 那么对所有整数c, a|bc – 若a|b, b|c, 则a|c

整除关系具有传递性. 它是偏序关系(partial order), <|,Z>是一个格

刘汝佳 黑书 课件 经典

素数和合数 如果大于1的正整数p仅有的正因子是1和p, 则称p为素数(prime) 大于1又不是素数的正整数称为合数 (compound) 如果n是合数, 则n必有一个小于或等于n1/2 的素因子

刘汝佳 黑书 课件 经典

算术基本定理 每个正整数都可以惟一地表示成素数的乘积，其 中素数因子从小到大依次出现(这里的“乘积” 可以有0个、1个或多个素因子)。 换句话说, 任意正整数n可以写成n=2a1*3a2*5a3*…, 其中a1,a2,a3等为非负整数 这个定理也叫做惟一分解定理。它是一个定理而 不是公理！虽然在大多人看来，它是“显然成立” 的，但它的确是需要证明的定理

刘汝佳 黑书 课件 经典

除法和同余 令a为整数，d为正整数，那么有惟一 的整数q和r,其中0≤r<d,使得a=dq+r 可以用这个定理来定义除法：d叫除数， a叫被除数，q叫商，r叫余数。如果两 个数a,b除以一个数c的余数相等，说a 和b关于模c同余，记作a≡b(mod c)

刘汝佳 黑书 课件 经典

同余 为什么有同余? 13241234…1+432435..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)

刘汝佳 黑书 课件 经典

定理的证明 使用惟一分解定理. 设 a1 a2 an b1 b2 bn a p1 p2 pn , b p1 p2 pn 则有:gcd(a, b) p1min(a1 ,b1 )max(a1 ,b1 )

p2p2

min(a2 ,b2 )max(a2 ,b2 )

pn pn

min(an ,bn )

lcm(a, b) p1

max(an ,bn )

容易验证定理成立

刘汝佳 黑书 课件 经典

例题：佳佳的困惑 给出一个数N,含数字1、2、3、4,把N的 所有数字重新排列一下组成一个新数，使 它是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和k+1互素, 因此– 要么k是完全平方数 – 要么k/2是完全平方数

分别设k=m2和2m2, 枚举m

刘汝佳 黑书 课件 经典

例题：齿轮 假设有三种齿轮：6齿，12齿，30齿。想要实现4 : 5的比例，一种可行方案如下：

给定可用的齿轮(每种均有无穷多),设计一系列 传输c1 : d1, c2 : d2, …, cm : dm,使得其综合比例 (c1c2c3…cm)/(d1d2d3…dm)为给定值a:b。 给定齿轮的齿数为5到100,a和b不超过10000。

刘汝佳 黑书 课件 经典

分析 使用惟一分解定理, 单独考虑各个素因子 c1 = p1a1*p2*a2*… c2 = p1b1*p2*b2*… … 则c1x*c2y=p1(x*a1+y*b1) *p2(x*a2+y*b2) 目标a:b = p1z1 * p2z2 … x*a1+y*b1=z1; x*a2+y*b2=z2

刘汝佳 黑书 课件 经典

分析 第i个齿轮的使用情况用xi表示，xi>0表示用 在分子xi次，xi<0表示用在分母-xi次。 由于ai<=100,只需要考虑100以内的25个 素数 考虑每个素数pi的指数，可以构造一个线性 方程，共25个等式 分子分母个数相等，故所有xi的和为0, 消元后枚举独立变量

刘汝佳 黑书 课件 经典

例题：破解RSA 给定M个数，它们的质因子在前T个质数范 围内。求这M个数组成集合的满足如下条件 的非空子集个数：子集中所有数的积为完 全平方数。

刘汝佳 黑书 课件 经典

分析 首先将读入的M个数，分解质因数，并对每 个质因数出现次数的奇偶性进行记录。 设x[i]=0或1代表是否使用第i个数。可以列 出一个关于x[i](1<=i<=m)的位方程组(乘积 的所有质因数出现次数均为偶数)。 解该方程组，检查最后有多少自变量，设 有n个，那么结果应该是2n-1(除去空集)。 时空复杂度均为O(M2)

本文来源：https://www.bwwdw.com/article/b3uj.html