数论和计算几何.pptVIP

数论和计算几何

12/30/2024数论方面

12/30/2024整除两个整数a和b(a0)，如果存在一个整数c，满足a*c=b，那么称为a整除b，符号记为a|b。

12/30/2024mod运算给定一个正整数p，任意一个整数n，一定存在等式n=kp+r其中k、r是整数，且0≤rp，称呼k为n除以p的商，r为n除以p的余数。我们定义r为nmodp。

12/30/2024mod运算的性质(a+b)modc=((amodc)+(bmodc))modc(a-b)modc=((amodc)-(bmodc))modc(a*b)modc=((amodc)*(bmodc))modc注意：(a/b)modc的求法需要运用乘法逆元，有关资料可以上网查找，这里就不阐述了。

12/30/2024素数与合数如果一个大于1的整数，其因数只有1和其本身，那么那么称这个整数为素数，否那么为合数。1既不是素数也不是合数

12/30/2024素数判断假设整数c是一个合数，那么他必然有一个=sqrt(n)的因子，因为假设a是c的因子，必然存在因子b，使得a*b=c，而a和b假设同时大于sqrt(c)，那么a*bc，不符合条件，所以上述结论成立。因此我们判断一个数字n是否是素数，只需枚举2到sqrt(n)中是否存在n的因子，不存在那么为素数，存在的话那么是合数。时间复杂度O(sqrt(n)).

12/30/2024假设一个数字p是合数，用上述作法也可以求出这个数字的约数个数和其约数具体是哪些数字。假设数字a是数字p的约数(a=sqrt(p))，那么p/a也是其约数。

12/30/2024筛法筛法是用来求不超过整数n(n1)的所有质数的一种方法。最常用的筛法是埃拉托斯特尼筛法，具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。当然还有其他的筛法，这里就不一一表达了。

12/30/2024算术根本定理任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=(P1^a1)*(P2^a2)......(Pn^an),这里P1P2...Pn是质数，其诸方幂ai是正整数。

12/30/2024质因数分解我们可以从2到sqrt(n)枚举整数n的质因数，如果数字i满足i|n，那么i就是p的一个质因子，这是我们将n/i。当然n有可能包含多个i，所以还需要记录出现了多少个i，然后依次枚举下去。当然这里不会出现枚举的数字不是质因子的情况，因为如果当前枚举的数字是合数p，那么这个合数的质因数在之前就已经从n中剔除掉了，此时的n是无法被p整除的。

12/30/2024假设最后的n不为1，那么此时的n也为原来的n的质因子。因为一个整数N可以分解为有限个质数的乘积N=(P1^a1)*(P2^a2)......(Pn^an)因此其约数个数除了之前提到的方法进行统计，还可以使用其分解质数的个数，来进行统计F(N)=(1+a1)*(1+a2)*.....(1+an)

12/30/2024例题N因子给你一个整数N(N=20000),要求你求出至少包含N个因子的最小整数是多少？

12/30/2024首先对于一个数求其约数个数之前我们有提到过两种方法，这题我们假设是一个个数枚举过去，找到一个最小的数字其约数个数=N，那么用这两种中哪一种方法求约数个数，很明显都是要不可行的。

12/30/2024但是利用第二种求约数总数的方法，我们可以设定一个约数总数M，求出一个包含M个约数的整数(但是不一定是最小的包含M个约数的整数)。假设我们要求构造一个有x个约数的数字y，那么我们可以将x进行分解x=a1*a2*...an因为y是由我们构造的，因此y的质因子可以随便选取，为了使的y尽量小，我们可以从小到大选择质因子，同时使得a1a2a3...an，新构造的数字为y=2^(a1-1)*3^(a2-1)*5^(a3-1)*....*P^(an-1)

12/30/2024具体实现我们可以用有哪些信誉好的足球投注网站，设一个有哪些信誉好的足球投注网站上界M，用前面所述的方法去枚举每个质因数的指数构造不超过m的整数。如果有构造数因子数超过了n并且比当前答案要优，那么更新答案。

12/30/2024而上界我们也可以大致的进行一个估计，估计的数字为第1个素数到第log(20000)+1个素数的乘积，由前面分析的情况可以