数论和计算几何

1、数论和计算几何数论和计算几何1/11/2022 数论方面数论方面 1/11/2022整除整除 两个整数a和b(a0)，如果存在一个整数c，满足a*c=b，则称为a整除b，符号记为a|b。1/11/2022modmod运算运算 给定一个正整数p，任意一个整数n，一定存在等式n = kp + r 其中k、r是整数，且 0 r p，称呼k为n除以p的商，r为n除以p的余数。我们定义r为n mod p。1/11/2022 mod运算的性质(a+b)mod c=(a mod c)+(b mod c)mod c(a-b)mod c=(a mod c)-(b mod c)mod c(a*b)mod c=(a

2、 mod c)*(b mod c)mod c注意：(a/b)mod c的求法需要运用乘法逆元，有关资料可以上网查找，这里就不阐述了。1/11/2022素数与合数素数与合数 如果一个大于1的整数，其因数只有1和其本身，那么则称这个整数为素数，否则为合数。 1既不是素数也不是合数1/11/2022素数判断素数判断 若整数c是一个合数，则他必然有一个c，不符合条件，所以上述结论成立。 因此我们判断一个数字n是否是素数，只需枚举2到sqrt(n)中是否存在n的因子，不存在则为素数，存在的话则是合数。 时间复杂度O(sqrt(n).1/11/2022 若一个数字p是合数，用上述作法也可以求出这个数字的约

3、数个数和其约数具体是哪些数字。若数字a是数字p的约数(a1)的所有质数的一种方法。 最常用的筛法是埃拉托斯特尼筛法，具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。 当然还有其他的筛法，这里就不一一叙述了。1/11/2022算术基本定理算术基本定理 任何一个大于1的自然数N，都可以唯一分

4、解成有限个质数的乘积 N=(P1a1)*(P2a2).(Pnan) , 这里P1P2.Pn是质数，其诸方幂ai 是正整数。1/11/2022质因数分解质因数分解 我们可以从2到sqrt(n)枚举整数n的质因数，如果数字i满足i|n，则i就是p的一个质因子，这是我们将n/i。当然n有可能包含多个i，所以还需要记录出现了多少个i，然后依次枚举下去。 当然这里不会出现枚举的数字不是质因子的情况，因为如果当前枚举的数字是合数p，则这个合数的质因数在之前就已经从n中剔除掉了，此时的n是无法被p整除的。1/11/2022 若最后的n不为1，则此时的n也为原来的n的质因子。 因为一个整数N可以分解为有限个质

5、数的乘积N=(P1a1)*(P2a2).(Pnan) 因此其约数个数除了之前提到的方法进行统计，还可以使用其分解质数的个数，来进行统计 F(N)=(1+a1)*(1+a2)*.(1+an)1/11/2022例题例题 N因子 给你一个整数N(N=N，那么用这两种中哪一种方法求约数个数，很明显都是要不可行的。1/11/2022 但是利用第二种求约数总数的方法，我们可以设定一个约数总数M，求出一个包含M个约数的整数(但是不一定是最小的包含M个约数的整数)。 假设我们要求构造一个有x个约数的数字y，那么我们可以将x进行分解 x=a1*a2*.an 因为y是由我们构造的，因此y的质因子可以随便选取，为了

6、使的y尽量小，我们可以从小到大选择质因子，同时使得a1a2a3.an，新构造的数字为 y=2(a1-1)*3(a2-1)*5(a3-1)*.*P(an-1)1/11/2022 具体实现我们可以用搜索，设一个搜索上界M，用前面所述的方法去枚举每个质因数的指数构造不超过m的整数。如果有构造数因子数超过了n并且比当前答案要优，那么更新答案。1/11/2022 而上界我们也可以大致的进行一个估计，估计的数字为第1个素数到第log(20000)+1个素数的乘积，由前面分析的情况可以得知这是一个包含2(log(20000)+1)个因子的数字，超过了数据的最大范围。因此题目所要求的最小数字一定在这个数字的范

7、围之内。1/11/2022例题例题 给定正整数a与b，求a到b之间素数的个数。 1=a=b=1000000000 b-a=10000001/11/2022 如果直接把a到b之间的数字一个个判断它们是否是素数显然是行不通的。 如果直接用筛法筛出b以内所有的素数，很显然还是行不通的。 那么对于这么大的数据，怎么做才能行得通呢？1/11/2022 之前证明过一个整数n是合数的话在2到sqrt(n)以内必然会有一个因子，而这个因子有可能是合数或者质数，如果是合数的话那么很显然这个合数因子可以拆分成更小的质数因子，因此可以得出结论：整数n是合数的话在2到sqrt(n）以内必然会有一个质因子。 有了这样的

8、结论，那么这题的思路就很明朗了。1/11/2022 首先我们筛出1到sqrt(b)之内所有的质数，再用这些质数去筛出a到b之内的质数，如果a到b之间的数字i没有一个小于sqrt(b)的质因子，那么他就是质数，否则就是合数。这样一来就可以算出答案了。1/11/2022GCDGCD 最大公约数(GCD)：设a和b为两个不全为0的整数，能使c|a并且c|b的最大整数c，称c为a与b的最大公约数1/11/2022 求gcd的常用解法：辗转相除法 gcd(a,b)=gcd(b,a mod b) 证明：a可以表示成a=kb+r则r=a mod b。 假设d是a,b的一个公约数，则d|a,d|b，而r=a-

9、kb，因此d|r。 因此d也是（b,a mod b）的公约数。 因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证。 时间复杂度O(logn) 1/11/2022 多个数的gcd gcd(a,b,c)=gcd(a,gcd(b,c)1/11/2022LCMLCM 最小公倍数(LCM):设a和b为两个不全为0的整数，能使a|c并且b|c的最小整数c，称c为a与b的最小公倍数 a*b=gcd(a,b)*lcm(a,b)1/11/2022 LCM的解法 lcm(a,b)=a*b/gcd(a,b) 多个数的LCM lcm(a,b,c)=a*b*c/gcd(a,b,c)1

10、/11/2022 例题1 noip2009Hankson的趣味题 n组数据 每组数据给定正整数a0,a1,b0,b1，设某未知正整数为X，X满足: 1.X和a0的最大公约数是a1。 2.X和b0的最小公倍数是b1。 求满足上述条件的正整数X的个数 数据范围 n=2000 1=a0,a1,b0,b1=t2,t3t2，则s=t2，若t1=t2，则s=t2 2.若t3t4，则s=t4，若t3=t4，则s=t4 将1和2得到的s集合进行并集，如果为空集，则表示无解，直接输出0，否则用乘法原理，将得出的s的个数乘进答案中。1/11/2022 例题2 设有两个正整数集A和B，如果正整数n既是A中所有元素的

11、公倍数，又是B中所有元素的公约数，则n为因子约数。 请找出有多少个n。正整数集A有x个数，正整数集有y个数（1=x,y=50,1=ai,bi=1000000000) 1/11/2022 和第一题其实差不多，我们分别求出正整数集A的最小公倍数X和正整数集B的最大公约数Y，因为可行的因子约数质因数分解后的每个质因数个数的范围和X、Y有关，所以把X和Y进行质因数分解，可以和上题一样，对于某个质因数pi，若x中所包含的pi个数与y中所包含的pi个数的交集为空集，则判定为无解，否则统计进答案中。1/11/2022互质互质 当N个整数的最大公约数为1时，称这N个数互质。1/11/2022欧拉函数欧拉函数

12、对正整数n，欧拉函数(n)是小于或等于n的正整数中与n互质的数的数目。 (x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4).(1-1/pn),其中p1, p2pn为x的所有质因数，x是不为0的整数。1/11/2022快速幂快速幂 快速幂是用来快速计算an mod p的一种方法。 如果n是偶数则an=a(n/2)*a(n/2) 如果n是奇数则an=a(n/2)*a(n/2)*a 如果在最后才进行mod p可能会溢出，根据之前说的mod运算的性质，我们在递归时可以边做边取模。1/11/2022同余同余 两个整数a,b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余

13、 记作a b(mod m)1/11/2022扩展欧几里得扩展欧几里得 扩展欧几里得算法可以求出方程ax+by=gcd(a,b)的一组解。 在欧几里得算法中，当b=0时，此时a则为原a、b的最大公约数，此时满足上面方程的解为x=1，y=0。 通过递归，若已知bx+(a mod b)y=gcd(a,b)的解x和y 则gcd(a,b)=bx+(a mod b)y =bx+(a-a/b*b)y =ay+b*(x-a/b*y) 所以x=y,y=x-a/b*y 由此可知ax+by=gcd(a,b)的解，不断的向上回溯，最后得到结果 1/11/2022 例题 【noip2012 D2】同余方程求关于x的同余

14、方程ax 1 (mod b)的最小正整数解。数据保证一点有解。 (2=a,b=2000000000)1/11/2022 这里可以把方程转换成ax mod b=1，进而再转化成ax+by=1。 ax+by=1有解的充要条件为d=gcd(a,b)=1 证明:(1)若ax+by=1有解则方程左边必能被d整除，而右边也需要能被d整除，因此d=1。(2)存在一系列正整数或负整数x使得ax+by=d=1结合上述两点得证。1/11/2022 这里求得的只是ax+by=1的一组解，而题目要求x需要是最小正整数。 假设求出来的解是x0和y0，那么其余的解为 x=x0+b*t y=y0-a*t 由上式就可以求出a

15、x1(mod b)的最小正整数解。1/11/2022 扩展欧几里得最常见的用途就是解不定方程ax+by=c，当然还有其他用途，但是在这里我就不深入阐述了，如果有感兴趣的同学可以自己上网搜索相关资料。1/11/2022 计算几何方面计算几何方面1/11/2022浮点误差的处理浮点误差的处理 因为计算机处理浮点数会有精度问题，比如正确的结果应该为0，可是计算机计算出来的结果却0.000000001，因此我们实现程序的时候应该记得对误差进行处理。1/11/2022 具体程序 funtion sgn(x:extended):integer begin if abs(x)eps then sgn:=1

16、else sgn:=-1; end;1/11/2022向量与叉积向量与叉积 向量：以(0,0)为起点到以(x,y)为终点的有向线段。 叉积：向量A(x1,y1)和向量B(x2,y2)的叉积=x1y2-x2y1，即|A|B|sin(a,b)1/11/2022 叉积有一个很重要的性质，它可以通过符号来判断两向量间的顺逆时针关系（定义顺逆时针度数为180度内） 若P*Q0,则P在Q顺时针方向。 若P*Q0,则P在Q逆时针方向。 若P*Q=0，则P与Q共线，但可能同向也有可能反向。1/11/2022 叉积还有一个性质，叉积会等于向量A、B作为邻边围成的平行四边形OACB的有向面积,要注意的是有向面积有

17、正有负，我们将其取模后，即可得到平行四边形OACB的面积。1/11/2022多边形面积多边形面积 叉积可用于多边形面积的作法，具体作法是把原点与多边形的每个顶点连一条边，然后依次求出多边形相邻两个顶点与原点构成的向量的叉积，取其总和后在取摸除以2就是该多边形面积。1/11/2022例题例题 POJ2318TOY 一个矩形箱子，左上角与右下角的坐标给出，里面有n块板把箱子里的空间分隔成n+1个分区，给出这些板在上边的x坐标、下边的x坐标，以及m个玩具的坐标，求这些分区里的玩具数目。 n,m=5000。1/11/2022 首先我们可以把隔板从左到右进行排序。 一个分区是由两个隔板形成的，而判断一个

18、玩具是否在一个分区里面，我们可以一一枚举两个相邻的隔板，运用之前说的叉积的性质，来判断点是否在分区内。如果点在两线段同侧，则不在该分区内，否则贼在分区内。 该算法时间复杂度O(n2)，足以通过所有数据点，如果用二分来实现算法，可以优化到O(nlogn)。1/11/2022线段位置关系线段位置关系 我们可以通过判断线段是否跨立和比较坐标来判断线段是否相交、重合或者分离。 首先判断是否互相跨立就是用叉积的性质来判断a和b是否在cd异侧，c和d是否在ab异侧。 当然通过上述的作法还不够，因为如果上述作法得出的叉积都是0，那么说明两线段共线，而共线的情况有分离相交和重合，这是我们可以比较坐标的关系来求

19、出线段的位置关系。1/11/2022凸包凸包 点集Q的凸包是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。 一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题。1/11/2022 求解凸包的算法有好几种，这里介绍一种最好理解的方法，其他方法各位同学感兴趣的话可以上网搜索资料(Graham算法、快速凸包算法等),这里就不介绍了。 这里介绍的算法名字叫做卷包裹算法。1/11/2022 该算法可以这样理解:在空地上树立着一堆木桩，在一个最外侧的木桩绑上一根很长绳子，然后顺时针或者逆时针绕一圈。当再一次回到这个起点木桩时，可以保证绳子正好卡主了所有外围的木桩，并得到一个凸包

20、。1/11/2022 首先需要找到一个在凸包上的点，这里我们可以找最左边的点，如果有多个点满足条件，可以在这些满足条件的点中选一个最下面的点。找到后加入凸包。 然后以这个点为准点，用向量的叉积找出除这个点以外最外侧的点。并把这个点加入凸包。(如果有多个点满足条件，如果需要保留凸包上的点，则在这些满足条件的点中选一个最近的。若不保留，则选择一个最远的)。 然后用这个新找到的点，在进行以上步骤。 算法的终止条件就是找到的最外侧点为最开始的起点。 该算法的时间复杂度为O(NM)。N为点集中点的总数，M为在凸包中的点的数目。1/11/2022例题例题 题目输入一组凸包上的点，这些点只会在凸包顶点或者凸包边上，问能否添加一些点，构造出一个更大的新凸包，使得新凸包包含原凸包上的所有的点。1/11/2022 首先我