NOIP数论

素数筛法O(NlogN)算法不再赘述介绍一种O(N)算法：将i从2到N扫描从前i未被筛过则存入prime数组用j从1循环，用i*prime[j]筛素数，若imodprime[j]=0跳出不难发现，每个合数被删仅一次x=a^k1*b^k2(a,b为素数,ab)i=a^(k1-1)*b^k2prime[j]=a时x被筛去复杂度为O(N)for(i=2;i=n;i++){if(!hash[i])prime[++tot]=i;for(j=1;prime[j]*i=n;j++){hash[prime[j]*i]=1;if(i%prime[j]==0)break;}}最大公约数与最小公倍数高精度GCD?模拟单精度实现过程太过麻烦设a=b，则Gcd(a,b)=①Gcd(a/2,b/2)*2……a%2=0b%2=0②Gcd(a,b/2)……a%2=1b%2=0③Gcd(a/2,b)……a%2=0b%2=1④Gcd(b,a-b)……a%2=1b%2=1为什么是log级别的？(NOIp2009)已知Gcd(x,a0)=a1Lcm(x,b0)=b1求满足条件的x个数(a0,a1,b0,b1=2,000,000,000，2000组数据)x=a^kx*txa0=a^ka0*ta0a1=a^ka1*ta1b0=a^kb0*tb0b1=a^kb1*tb1min(kx,ka0)=ka1max(kx,kb0)=kb1若ka0=ka1则kx=ka1否则kx=ka1若kb0=kb1则kx=kb1否则kx=kb1可由此确定每个素数因子的范围乘法原理求总解数sqrt(2,000,000,000)内仅有4000+素数AC扩展欧几里得：如何求解ax+by=gcd(a,b)回顾欧几里得算法intgcd(inta,intb){returnb?gcd(b,a%b):a;}递归到底时a=gcd(a,b)，b=0，令x=1，y=0，满足ax+by=gcd(a,b)a%b=a-a/b*bax+by=c-bx’+(a-a/b*b)y’=cxa+yb=c-y’a+(x’-a/b*y’)b=c回溯时令x=y’y=x’-a/b*y’代码求ax+by=gcd(a,b)#includestdio.hintextended_gcd(inta,intb,int*x,int*y){intret,tmp;if(!b){*x=1;*y=0;returna;}ret=extended_gcd(b,a%b,x,y);tmp=*x;*x=*y;*y=tmp-a/b*(*y);returnret;}intmain(){inta,b,x,y,z;scanf(%d%d,&a,&b);z=extended_gcd(a,b,&x,&y);printf(%d%d%d\n,z,x,y);system(pause);return0;}求解ax+by=c?判断c是否被gcd(a,b)整除，整除则有解，反之无解求解ax+by=gcd(a,b)若ax+by=gcd(a,b)的解为(x’,y’)则ax+by=c的解(x,y)=(c/gcd(a,b)*x’,c/gcd(a,b)*y’)如何求出不定方程的所有整数解？(x+k*b/gcd(a,b)，y-k*a/gcd(a,b))为所有合法解其中k∈Z排列与组合排列数：N个不同物体不重复地取M个做排列的方法数P(N,M)=N!/(N-M)!组合数：N个不同物体不重复地选取M个的方法数C(N,M)=N!/((N-M)!*M!)可重排列：K种元素，重数分别为n1,n2,…,nk，所有n=Σni个元素的全排列数为n!/(n1!n2!..nk!)K种元素，重数均为无限大，选取r的的组合数为C(r+K-1,r)可以转化为矩阵内从左上角到右下角只能向右走或下走的方法数问题组合公式的推论c(n,m)=c(n,n-m);c(n,m)=c(n-1,m-1)+c(n-1,m)卡特兰数h(n)=C(2n,n)/(n+1)(n=0,1,2,...)错排公式递推式：M(n)=(n-1)[M(n-2)+M(n-1)]特殊地，M⑴=0,M⑵=1错排公式为M(n)=n!(1/2!-1/3!+…..+(-1)^n/n!)容斥原理研究有限集合的交或并的计数。[DeMorgan定理]论域U，补集A{|}AxxUxA且,有容斥原理(a)ABAB(b)ABABDeMogan定理的推广：设1,2,...,nAAAU是的子集212......nnAAAAA1则(a)A容斥原理容斥原理最简单的计数问题是求有限集合A和B的并的元素数目。显然有即具有性质A或B的元素的个数等于具有性质A和性质B的元素个数ABABAB(1)定理：定理：设1,2,...,nAAA是有限集合，则1211112......(1)...nnniijiijiknjnAAAAAAAAAAAnii=1jikj+A(4)容斥原理121211112.........(1)...nnnnniijiijjkninAAANAAAANAAAAAAAAnii=1jikjA-(5)容斥原理指的就是（4）和（5）式。容斥原理例4。求不超过120的素数个数。i例因，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。设为不超过120的数的倍数集，=2，3，5，7。i2357232527351201206040231201202417,571201202012,2310120120881415AAAAAAAAAAAA，，，，，，例3757235237257120120532135120423512022371201257AAAAAAAAAAAAA，，，，，例235723572325273537572352372573572357120AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA例120(60402417)(20128853)(4211)27.例注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7着四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求的不超过120的素数个数为：27+4-1=30例向量常用头文件#includemath.h计算几何中一般来说使用double型比较频繁，请注意数据类型的选择，该用实数的时候就用double，而float容易失去精度。判断double型的x是否为0，应当用xeps&&x-eps（或者fabs(x)eps），其中eps代表某个精度，常常取eps=0.000001，还有其他类似情况也要注意double类型的精度问题，int(x+eps)，避免x=4.999999999圆周率取3.141592654或者更精确，或者用acos(-1)角度制和弧度制的转换，C/C++中的三角函数均为弧度制尽量少用除法，开方，三角函数，容易失去精度。用除法时注意除数不为0输出的时候要小心-0.00000，比如a=-0.0000001，printf(“%.5lf”,a);计算几何中经常使用向量，而且基本上都是二维的，下面用αβγ代表三个向量α=(x[0],y[0])β=(x[1],y[1])γ=(x[2],y[2])某些题目需要经常使用向量运算，因此对于这类问题最好建立构造类型或者类来表示向量，并将向量之间的运算进行重载一般需要重载加法，减法，和向量乘法structpoint{//构造点的数据类型，也可作向量使用doublex;doubley;}v1,v2;pointoperator+(pointp1,pointp2);doubleoperator*(pointp1,pointp2);加法γ=α+β=（x[0]+x[1],y[0]+y[1]）满足平行四边形法则图形表示减法图形表示γαβγβα向量有两种乘法，内积（数量积，点积）和外积（向量积，叉积），一般是要根据题目需要选择其中一个重载，多数情况是重载外积，其中内积α·β=x[0]*x[1]+y[0]*y[1]外积α×β=x[0]*y[1]–x[1]*y[0]=x[0]y[0]x[1]y[1]内积的几何意义：α在β的投影α’与β的长度乘积外积的几何意义：α和β所张成的平行四边形的有向面积外积在计算几何的题目当中经常使用αβα'αβ判断外积的符号，右手定则如图，α×β0，β×α0如果α×β==0则等价于两个向量共线（同向或反向），可以用此判断三点共线问题。当然，这里的==0在实际编程的时候要用一个精度来控制αβ利用外积求三角形面积已知三个顶点坐标为(a[0],b[0]),(a[1],b[1]),(a[2],b[2])，则三角形面积为注意别忘记取绝对值，这里利用面积是否为0也可以考察三点共线问题这个方法求面积比海伦公式或者其他方法要好a[1]-a[0]b[1]-b[0]fabs/2.0a[2]-a[0]b[2]-b[0]由求三角形面积的方法可以推广求凸多边形面积如图，从一固定点出发，向其他各点引辅助线，这样就分割成了若干个三角形，利用上式求出每个三角形的面积再相加即可。ABCDEF整点多边形是指顶点的横纵坐标均为整数由外积导出的面积计算公式可以看出，整点多边形的面积或为整数，或为整数/2.Pick公式：整点多边形的面积=内部整点个数+边上的整点个数/2-1.NKOJ1159:Triangle计算几何中的公式有不少，需要积累如何判断点是否在三角形内部？此点与三角形三个顶点相连，出现三个三角形，如果这三个三角形的面积之和等于原三角形面积，那么该点在内部推广：可用来判断点是否在凸多边形内部利用三点共线的等价条件α×β==0直线上取两不同点P1,P2，若点P在直线上，则fabs((P1-P)×(P2-P))eps如果该题目需要编写求三角形面积的函数，那直接判断这三个点形成的三角形面积是否eps判断点P(x,y)是否在线段P1P2上，其中P1(x1,y1),P2(x2,y2)需要验证两条（1）点P在P1P2所在直线上，即三点共线（2）点P在P1P2为对角线的矩形内其中（2）利用min(x1,x2)=x=max(x1,x2)&&min(y1,y2)=y=max(y1,y2)用高斯消元法解线性方程组a1,1x1+a1,2x2+……+a1,nxn=b1a2,1x1+a2,2x2+……+a2,nxn=b2……an,1x1+an,2x2+……+an,nxn=bn下面是n元线性方程组的一般形式：我们可以把它表示为增广矩阵的形式：a1,1a1,2……a1,nb1a2,1a2,2……a2,nb2……an,1an,2……an,nbn2-131425412072-1314-122.5-1.56.52-1314-12-0.8755.25×2×0.5×0.625得出：x3=5.25/(-0.875)=-6x2=(2-(-1)x3)/4=-1x1=(1-(-1)x2-3x3)/2=9a1,1(1)a1,2(1)……a1,n(1)b1(1)a2,1(1)a2,2(1)……a2,n(1)b2(1)……an,1(1)an,2(1)……an,n(1)bn(1)注：用上标(k)表示第k次消元前的状态第1次消元，第1行的乘数：（i=2,3,…,n）)1(1,1)1(1,1,aaiima1,1(1)a1,2(1)……a1,n(1)b1