数论和计算几何

1、数论和计算几何,6/18/2020,数论方面,6/18/2020,整除,两个整数a和b(a0)，如果存在一个整数c，满足a*c=b，则称为a整除b，符号记为a|b。,6/18/2020,mod运算,给定一个正整数p，任意一个整数n，一定存在等式n=kp+r其中k、r是整数，且0rp，称呼k为n除以p的商，r为n除以p的余数。我们定义r为nmodp。,6/18/2020,mod运算的性质(a+b)modc=(amodc)+(bmodc)modc(a-b)modc=(amodc)-(bmodc)modc(a*b)modc=(amodc)*(bmodc)modc注意：(a/b)modc的求法需要运用

2、乘法逆元，有关资料可以上网查找，这里就不阐述了。,6/18/2020,素数与合数,如果一个大于1的整数，其因数只有1和其本身，那么则称这个整数为素数，否则为合数。1既不是素数也不是合数,6/18/2020,素数判断,若整数c是一个合数，则他必然有一个c，不符合条件，所以上述结论成立。因此我们判断一个数字n是否是素数，只需枚举2到sqrt(n)中是否存在n的因子，不存在则为素数，存在的话则是合数。时间复杂度O(sqrt(n).,6/18/2020,若一个数字p是合数，用上述作法也可以求出这个数字的约数个数和其约数具体是哪些数字。若数字a是数字p的约数(a1)的所有质数的一种方法。最常用的筛法是埃

3、拉托斯特尼筛法，具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。当然还有其他的筛法，这里就不一一叙述了。,6/18/2020,算术基本定理,任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=(P1a1)*(P2a2).(Pnan),这里P1P2.a2a3.an，新构造的数字为

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

5、a=b=1000000000b-a=1000000,6/18/2020,如果直接把a到b之间的数字一个个判断它们是否是素数显然是行不通的。如果直接用筛法筛出b以内所有的素数，很显然还是行不通的。那么对于这么大的数据，怎么做才能行得通呢？,6/18/2020,之前证明过一个整数n是合数的话在2到sqrt(n)以内必然会有一个因子，而这个因子有可能是合数或者质数，如果是合数的话那么很显然这个合数因子可以拆分成更小的质数因子，因此可以得出结论：整数n是合数的话在2到sqrt(n）以内必然会有一个质因子。有了这样的结论，那么这题的思路就很明朗了。,6/18/2020,首先我们筛出1到sqrt(b)之内

6、所有的质数，再用这些质数去筛出a到b之内的质数，如果a到b之间的数字i没有一个小于sqrt(b)的质因子，那么他就是质数，否则就是合数。这样一来就可以算出答案了。,6/18/2020,GCD,最大公约数(GCD)：设a和b为两个不全为0的整数，能使c|a并且c|b的最大整数c，称c为a与b的最大公约数,6/18/2020,求gcd的常用解法：辗转相除法gcd(a,b)=gcd(b,amodb)证明：a可以表示成a=kb+r则r=amodb。假设d是a,b的一个公约数，则d|a,d|b，而r=a-kb，因此d|r。因此d也是（b,amodb）的公约数。因此（a,b）和（b,amodb）的公约数是

7、一样的，其最大公约数也必然相等，得证。时间复杂度O(logn),6/18/2020,多个数的gcdgcd(a,b,c)=gcd(a,gcd(b,c),6/18/2020,LCM,最小公倍数(LCM):设a和b为两个不全为0的整数，能使a|c并且b|c的最小整数c，称c为a与b的最小公倍数a*b=gcd(a,b)*lcm(a,b),6/18/2020,LCM的解法lcm(a,b)=a*b/gcd(a,b)多个数的LCMlcm(a,b,c)=a*b*c/gcd(a,b,c),6/18/2020,例题1noip2009Hankson的趣味题n组数据每组数据给定正整数a0,a1,b0,b1，设某未知正

8、整数为X，X满足:1.X和a0的最大公约数是a1。2.X和b0的最小公倍数是b1。求满足上述条件的正整数X的个数数据范围n=20001=t22.若t3t4，则s=t4，若t3=t4，则s=t4将1和2得到的s集合进行并集，如果为空集，则表示无解，直接输出0，否则用乘法原理，将得出的s的个数乘进答案中。,6/18/2020,例题2设有两个正整数集A和B，如果正整数n既是A中所有元素的公倍数，又是B中所有元素的公约数，则n为因子约数。请找出有多少个n。正整数集A有x个数，正整数集有y个数（1=x,y=50,1=ai,bi=1000000000),6/18/2020,和第一题其实差不多，我们分别求出

9、正整数集A的最小公倍数X和正整数集B的最大公约数Y，因为可行的因子约数质因数分解后的每个质因数个数的范围和X、Y有关，所以把X和Y进行质因数分解，可以和上题一样，对于某个质因数pi，若x中所包含的pi个数与y中所包含的pi个数的交集为空集，则判定为无解，否则统计进答案中。,6/18/2020,互质,当N个整数的最大公约数为1时，称这N个数互质。,6/18/2020,欧拉函数,对正整数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的整数。,6

10、/18/2020,快速幂,快速幂是用来快速计算anmodp的一种方法。如果n是偶数则an=a(n/2)*a(n/2)如果n是奇数则an=a(n/2)*a(n/2)*a如果在最后才进行modp可能会溢出，根据之前说的mod运算的性质，我们在递归时可以边做边取模。,6/18/2020,同余,两个整数a,b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余记作ab(modm),6/18/2020,扩展欧几里得,扩展欧几里得算法可以求出方程ax+by=gcd(a,b)的一组解。在欧几里得算法中，当b=0时，此时a则为原a、b的最大公约数，此时满足上面方程的解为x=1，y=0。通过递归，若已知b

11、x+(amodb)y=gcd(a,b)的解x和y则gcd(a,b)=bx+(amodb)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)的解，不断的向上回溯，最后得到结果,6/18/2020,例题【noip2012D2】同余方程求关于x的同余方程ax1(modb)的最小正整数解。数据保证一点有解。(2=a,b0,则P在Q顺时针方向。若P*Q0,则P在Q逆时针方向。若P*Q=0，则P与Q共线，但可能同向也有可能反向。,6/18/2020,叉积还有一个性质，叉积会等于向量A、B作为邻边围成的平行四边形OACB的有向面积,

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

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

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

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

16、能否添加一些点，构造出一个更大的新凸包，使得新凸包包含原凸包上的所有的点。,6/18/2020,首先我们考虑新添加的点可以添加在哪些地方，我们来看下图。,这是凸包的一部分，用虚线分成了区域A和区域B两部分，很明显可以看出新添加的点可能在区域A而不能在区域B。因为若添加在区域B，则点C就不可能出现新凸包中。,6/18/2020,但是区域A就都可以吗，其实也不是都行的，如下图,我们应该更细分线段CD附近的区域，区域E是不可以，和之前为什么不能再区域B是同一个道理，那么区域A就是可行区域。从全局上看，连续三边中，在中间的边和剩下两边的延长线围成的封闭区域中添加点，就可以满足题目的要求。,6/18/2020,知道了这一点，那么就比较容易理解什么情况下不会使得新凸包更大了，当封闭区域的面积为0的时候，就无法添加点使得新凸包比原凸包更大。当原凸包上的每条边上的点的数目都有至少三个的时候，是无法添加新的点的。实现程序时我们只要算出原凸包，然后判断每条边上点数的情况，就可以解出答案了。,6/18/2020,判断点是否在多