刘汝佳-1数论初步.ppt

《刘汝佳-1数论初步.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2005年浙江省队培训第1讲数论初步刘汝佳目录一、基本概念二、进位制三、模算术与方程四、杂题一、基本概念基本概念整除与约数、倍数.注意负数可整除性的基本性质若a

2、b,a

3、c,则a

4、(b+c)若a

5、b,那么对所有整数c,a

6、bc若a

7、b,b

8、c,则a

9、c整除关系具有传递性.它是偏序关系(partialorder),<

10、,Z>是一个格素数和合数如果大于1的正整数p仅有的正因子是1和p,则称p为素数(prime)大于1又不是素数的正整数称为合数(compound)如果n是合数,则n必有一个小于或等于n1/2的素因子算术基本定理每个正整数都可以惟一地表示成素数的乘积，其中素

11、数因子从小到大依次出现（这里的“乘积”可以有0个、1个或多个素因子）。换句话说,任意正整数n可以写成n=2a1*3a2*5a3*…,其中a1,a2,a3等为非负整数这个定理也叫做惟一分解定理。它是一个定理而不是公理！虽然在大多人看来，它是“显然成立”的，但它的确是需要证明的定理除法和同余令a为整数，d为正整数，那么有惟一的整数q和r，其中0≤r

12、2=24….7余数可以作为原数的一个signature(标记).如果标记下的运算错误,一定错误如果标记下的运算正确?最大公约数和最小公倍数令a和b是不全为0的两个整数，能使d

13、a和d

14、b的最大整数称为a和b的最大公约数，用gcd(a,b)表示，或者记为(a,b)。令a和b是不全为0的两个整数，能使a

15、d和b

16、d的最小整数称为a和b的最小公倍数，用lcm(a,b)表示，或者记为[a,b]定理:ab=gcd(a,b)*lcm(a,b)定理的证明使用惟一分解定理.设则有:容易验证定理成立例题：佳佳的困惑给出一个数N，含数字1、2、3、4，把N的所有数字重新排列一下组成一个新

17、数，使它是7的倍数。分析把数字1、2、3、4从中抽出，然后把其他数字按照原顺序排列（事实上，怎么排列都无所谓）组成自然数ww*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互素,因此要么

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

19、…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个数。可以列出

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