数论和计算几何

数论和计算几何2/2/2023数论方面2/2/2023整除两个整数a和b(a<>0)，如果存在一个整数c，满足a*c=b，则称为a整除b，符号记为a|b。2/2/2023mod运算给定一个正整数p，任意一个整数n，一定存在等式n=kp+r其中k、r是整数，且0≤r<p，称呼k为n除以p的商，r为n除以p的余数。我们定义r为nmodp。2/2/2023mod运算的性质(a+b)modc=((amodc)+(bmodc))modc(a-b)modc=((amodc)-(bmodc))modc(a*b)modc=((amodc)*(bmodc))modc注意：(a/b)modc的求法需要运用乘法逆元，有关资料可以上网查找，这里就不阐述了。2/2/2023素数与合数如果一个大于1的整数，其因数只有1和其本身，那么则称这个整数为素数，否则为合数。1既不是素数也不是合数2/2/2023素数判断若整数c是一个合数，则他必然有一个<=sqrt(n)的因子，因为若a是c的因子，必然存在因子b，使得a*b=c，而a和b若同时大于sqrt(c)，则a*b>c，不符合条件，所以上述结论成立。因此我们判断一个数字n是否是素数，只需枚举2到sqrt(n)中是否存在n的因子，不存在则为素数，存在的话则是合数。时间复杂度O(sqrt(n)).2/2/2023若一个数字p是合数，用上述作法也可以求出这个数字的约数个数和其约数具体是哪些数字。若数字a是数字p的约数(a<=sqrt(p))，则p/a也是其约数。2/2/2023筛法筛法是用来求不超过整数n(n>1)的所有质数的一种方法。最常用的筛法是埃拉托斯特尼筛法，具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。当然还有其他的筛法，这里就不一一叙述了。2/2/2023算术基本定理任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=(P1^a1)*(P2^a2)......(Pn^an),这里P1<P2<...<Pn是质数，其诸方幂ai是正整数。2/2/2023质因数分解我们可以从2到sqrt(n)枚举整数n的质因数，如果数字i满足i|n，则i就是p的一个质因子，这是我们将n/i。当然n有可能包含多个i，所以还需要记录出现了多少个i，然后依次枚举下去。当然这里不会出现枚举的数字不是质因子的情况，因为如果当前枚举的数字是合数p，则这个合数的质因数在之前就已经从n中剔除掉了，此时的n是无法被p整除的。2/2/2023若最后的n不为1，则此时的n也为原来的n的质因子。因为一个整数N可以分解为有限个质数的乘积N=(P1^a1)*(P2^a2)......(Pn^an)因此其约数个数除了之前提到的方法进行统计，还可以使用其分解质数的个数，来进行统计F(N)=(1+a1)*(1+a2)*.....(1+an)2/2/2023例题N因子给你一个整数N(N<=20000),要求你求出至少包含N个因子的最小整数是多少？2/2/2023首先对于一个数求其约数个数之前我们有提到过两种方法，这题我们若是一个个数枚举过去，找到一个最小的数字其约数个数>=N，那么用这两种中哪一种方法求约数个数，很明显都是要不可行的。2/2/2023但是利用第二种求约数总数的方法，我们可以设定一个约数总数M，求出一个包含M个约数的整数(但是不一定是最小的包含M个约数的整数)。假设我们要求构造一个有x个约数的数字y，那么我们可以将x进行分解x=a1*a2*...an因为y是由我们构造的，因此y的质因子可以随便选取，为了使的y尽量小，我们可以从小到大选择质因子，同时使得a1>a2>a3...>an，新构造的数字为y=2^(a1-1)*3^(a2-1)*5^(a3-1)*....*P^(an-1)2/2/2023具体实现我们可以用搜索，设一个搜索上界M，用前面所述的方法去枚举每个质因数的指数构造不超过m的整数。如果有构造数因子数超过了n并且比当前答案要优，那么更新答案。2/2/2023而上界我们也可以大致的进行一个估计，估计的数字为第1个素数到第log(20000)+1个素数的乘积，由前面分析的情况可以得知这是一个包含2^(log(20000)+1)个因子的数字，超过了数据的最大范围。因此题目所要求的最小数字一定在这个数字的范围之内。2/2/2023例题给定正整数a与b，求a到b之间素数的个数。1<=a<=b<=1000000000b-a<=10000002/2/2023如果直接把a到b之间的数字一个个判断它们是否是素数显然是行不通的。如果直接用筛法筛出b以内所有的素数，很显然还是行不通的。那么对于这么大的数据，怎么做才能行得通呢？2/2/2023之前证明过一个整数n是合数的话在2到sqrt(n)以内必然会有一个因子，而这个因子有可能是合数或者质数，如果是合数的话那么很显然这个合数因子可以拆分成更小的质数因子，因此可以得出结论：整数n是合数的话在2到sqrt(n）以内必然会有一个质因子。有了这样的结论，那么这题的思路就很明朗了。2/2/2023首先我们筛出1到sqrt(b)之内所有的质数，再用这些质数去筛出a到b之内的质数，如果a到b之间的数字i没有一个小于sqrt(b)的质因子，那么他就是质数，否则就是合数。这样一来就可以算出答案了。2/2/2023GCD最大公约数(GCD)：设a和b为两个不全为0的整数，能使c|a并且c|b的最大整数c，称c为a与b的最大公约数2/2/2023求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）的公约数是一样的，其最大公约数也必然相等，得证。时间复杂度O(logn)2/2/2023多个数的gcdgcd(a,b,c)=gcd(a,gcd(b,c))2/2/2023LCM最小公倍数(LCM):设a和b为两个不全为0的整数，能使a|c并且b|c的最小整数c，称c为a与b的最小公倍数a*b=gcd(a,b)*lcm(a,b)2/2/2023LCM的解法lcm(a,b)=a*b/gcd(a,b)多个数的LCMlcm(a,b,c)=a*b*c/gcd(a,b,c)2/2/2023例题1[noip2009]Hankson的趣味题n组数据每组数据给定正整数a0,a1,b0,b1，设某未知正整数为X，X满足:1.X和a0的最大公约数是a1。2.X和b0的最小公倍数是b1。求满足上述条件的正整数X的个数[数据范围]n<=20001<=a0,a1,b0,b1<=20000000002/2/2023如果数据范围很小，我们可以直接枚举X，把X带入条件1和条件2进行检验，可行的话就累加答案。这样的枚举可以进行优化，我们把枚举检验的对象变为a1的倍数，因为a1是x和a0的最大公约数，所以a1的倍数自然有可能是x，但是由于数据范围很大，这样的方法不能使我们拿到全部的分数2/2/2023我们从更细的地方进行思考，我们可以对最小公倍数和最大公约数进行分解质因数后的指数进行分析。将A和B两个整数进行分解质因数A=p1^a1+p2^a2+p3^a3+......B=p1^b1+p2^b2+p3^a3+......这样最小公倍数和最大公约数可表示为gcd(a,b)=p1^min(a1,b1)+p2^min(a2,b2)+p3^min(a3,b3)+.....lcm(a,b)=p1^max(a1,b1)+p2^max(a2,b2)+p3^max(a3,b3)+.....2/2/2023这样我们可以先用筛法预处理出trunc(sqrt(2000000000))以内全部的素数，用这些素数我们可以算出a0,a1,b0,b1每种质数因子的个数t1,t2,t3,t4设我们要求的x的每种质因数个数为S若数据合法，则t1>=t2,t3<=t4在数据合法的情况下，结合之前我们得出的最大公约数和最小公倍数质因数分解后指数的关系，我们可以求出S的范围1.若t1>t2，则s=t2，若t1=t2，则s>=t22.若t3<t4，则s=t4，若t3=t4，则s<=t4将1和2得到的s集合进行并集，如果为空集，则表示无解，直接输出0，否则用乘法原理，将得出的s的个数乘进答案中。2/2/2023例题2设有两个正整数集A和B，如果正整数n既是A中所有元素的公倍数，又是B中所有元素的公约数，则n为因子约数。请找出有多少个n。正整数集A有x个数，正整数集有y个数（1<=x,y<=50,1<=ai,bi<=1000000000)

2/2/2023和第一题其实差不多，我们分别求出正整数集A的最小公倍数X和正整数集B的最大公约数Y，因为可行的因子约数质因数分解后的每个质因数个数的范围和X、Y有关，所以把X和Y进行质因数分解，可以和上题一样，对于某个质因数pi，若x中所包含的pi个数与y中所包含的pi个数的交集为空集，则判定为无解，否则统计进答案中。2/2/2023互质当N个整数的最大公约数为1时，称这N个数互质。2/2/2023☆欧拉函数对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目。φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1,p2……pn为x的所有质因数，x是不为0的整数。2/2/2023快速幂快速幂是用来快速计算a^nmodp的一种方法。如果n是偶数则a^n=a^(n/2)*a^(n/2)如果n是奇数则a^n=a^(n/2)*a^(n/2)*a如果在最后才进行modp可能会溢出，根据之前说的mod运算的性质，我们在递归时可以边做边取模。2/2/2023同余两个整数a,b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余记作a≡b(modm)2/2/2023扩展欧几里得扩展欧几里得算法可以求出方程ax+by=gcd(a,b)的一组解。在欧几里得算法中，当b=0时，此时a则为原a、b的最大公约数，此时满足上面方程的解为x=1，y=0。通过递归，若已知bx'+(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)的解，不断的向上回溯，最后得到结果

2/2/2023例题

【noip2012D2】同余方程求关于x的同余方程ax≡1(modb)的最小正整数解。数据保证一点有解。(2<=a,b<=2000000000)2/2/2023这里可以把方程转换成axmodb=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结合上述两点得证。2/2/2023这里求得的只是ax+by=1的一组解，而题目要求x需要是最小正整数。假设求出来的解是x0和y0，那么其余的解为x=x0+b*ty=y0-a*t由上式就可以求出ax≡1(modb)的最小正整数解。2/2/2023扩展欧几里得最常见的用途就是解不定方程ax+by=c，当然还有其他用途，但是在这里我就不深入阐述了，如果有感兴趣的同学可以自己上网搜索相关资料。2/2/2023

计算几何方面2/2/2023浮点误差的处理因为计算机处理浮点数会有精度问题，比如正确的结果应该为0，可是计算机计算出来的结果却0.000000001，因此我们实现程序的时候应该记得对误差进行处理。2/2/2023具体程序funtionsgn(x:extended):integerbeginifabs(x)<=epsthensgn:=0elseifx>epsthensgn:=1elsesgn:=-1;end;2/2/2023向量与叉积向量：以(0,0)为起点到以(x,y)为终点的有向线段。叉积：向量A(x1,y1)和向量B(x2,y2)的叉积=x1y2-x2y1，即|A||B|sin(a,b)2/2/2023叉积有一个很重要的性质，它可以通过符号来判断两向量间的顺逆时针关系（定义顺逆时针度数为180度内）若P*Q>0,则P在Q顺时针方向。若P*Q<0,则P在Q逆时针方向。若P*Q=0，则P与Q共线，但可能同向也有可能反向。2/2/2023叉积还有一个性质，叉积会等于向量A、B作为邻边围成的平行四边形OACB的有向面积,要注意的是有向面积有正有负，我们将其取模后，即可得到平行四边形OACB的面积。2/2/2023多边形面积叉积可用于多边形面积的作法，具体作法是把原点与多边形的每个顶点连一条边，然后依次求出多边形相邻两个顶点与原点构成的向量的叉积，取其总和后在取摸除以2就是该多边形面积。2/2/2023例题POJ2318[TOY]一个矩形箱子，左上角与右下角的坐标给出，里面有n块板把箱子里的空间分隔成n+1个分区，给出这些板在上边的x坐标、下边的x坐标，以及m个玩具的坐标，求这些分区里的玩具数目。n,m<=5000。2/2/2023首先我们可以把隔板从左到右进行排序。一个分区是由两个隔板形成的，而判断一个玩具是否在一个分区里面，我们可以一一枚举两个相邻的隔板，运用之前说的叉积的性质，来判断点是否在分区内。如果点在两线段同侧，则不在该分区内，否则贼在分区内。该算法时间复杂度O(n^2)，足以通过所有数据点，如果用二分来实现算法，可以优化到O(nlogn)。2/2/2023线段位置关系我们可以通过判断线段是否跨立和比较坐标来判断线段是否相交、重合或者分离。首先判断是否互相跨立就是用叉积的性质来判断a和b是否在cd异侧，c和d是否在ab异侧。当然通过上述的作法还不够，因为如果上述作法得出的叉积都是0，那么说明两线段共线，而共线的情况有分离相交和重合，这是我们可以比较坐标的关系来求出线段的位置关系。2/2/2023凸包点集Q的凸包是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题。2/2/2023求解凸包的算法有好几种，这里介绍一种最好理解的方法，其他方法各位同学感兴趣的话可以上网搜索资料(Graham算法、快速凸包算法等),这里就不介绍了。这里介绍的算法名字叫做"卷包裹"算法。2/2/2023该算法可以这样理解:在空地上树立着一堆木桩，在一个最外侧的木桩绑上一根很长绳子，然后顺时针或者逆时针绕一圈。当再一次回到这个起点木桩时，可以保证绳子正好卡主了所有外围的木桩，并得到一个凸包。2/2/2023首先需要找到一个在凸包上的点，这里我们可以找最左边的点，如果有多个点满足条件，可以在这些满足条件的点中选一个最下面的点。找到后加入凸包。然后以这个点为准点，用向量的叉积找出除这个点以外最外侧的点。并把这个点加入凸包。(如果有多个点满足条件，如果需要保留凸包上的点，则在这些满足条件的点中选一个最近的。若不保留，则选择一个最远的)。然后用这个新找到的点，在进行以上步骤。算法的终止条件就是找到的最外侧点为最开始的起点。该算法的时间复杂度为O(NM)。N为点集中点的