当前位置:首页 >> 学科竞赛 >>

NOIP数论


? ? ? ? ? ?

素数筛法 O(NlogN)算法不再赘述 介绍一种O(N)算法: 将i从2到N扫描 从前i未被筛过则存入prime数组 用j从1循环,用i*prime[j]筛素数,若i mod prime[j] = 0 跳出
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; } }

不难发现,每个合数被删仅一次 x = a^k1 * b^k2 ( a,b 为素数,a<b) i = a^(k1-1) * b^k2 prime[j] = a 时 x 被筛去 复杂度为O(N)

? ? ?

最大公约数与最小公倍数
高精度GCD? 模拟单精度实现过程太过麻烦

? ? ? ? ? ?
?

设a>=b,则 Gcd(a,b)= ①Gcd(a/2,b/2) *2 ②Gcd(a,b/2) ③Gcd(a/2,b) ④Gcd(b,a-b)

……a%2=0 ……a%2=1 ……a%2=0 ……a%2=1

b%2=0 b%2=0 b%2=1 b%2=1

为什么是log级别的?

? ? ? ? ? ? ? ? ? ? ? ? ?

(NOIp 2009) 已知 Gcd(x,a0)=a1 Lcm(x,b0)=b1 求满足条件的x个数 (a0,a1,b0,b1<=2,000,000,000,2000组数据)
x = a^kx * tx a0= a^ka0 * ta0 a1= a^ka1 * ta1 b0= a^kb0 * tb0 b1= a^kb1 * tb1 min (kx,ka0)=ka1 max(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)
? ? ? ? ? ? ? ?

回顾欧几里得算法 int gcd(int a,int b) { return b?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)
#include <stdio.h> int extended_gcd(int a, int b, int *x, int *y) { int ret, tmp; if (!b) { *x = 1; *y = 0; return a; } ret = extended_gcd(b, a % b,x, y); tmp = *x; *x = *y; *y = tmp - a / b * (*y); return ret; } int main() { int a,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"); return 0; }

? ? ? ? ? ? ? ?

求解 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(n1,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

A ? {x | x ?U 且x ? A} ,有
(a) A ? B ? A ? B

(b) A ? B ? A ? B

容斥原理
DeMogan定理的推广:设 A1, A2 ,..., An是U的子集

则 (a)A1 ? A2 ? ... ? An ? A1 ? A2 ? ... ? An

容斥原理
最简单的计数问题是求有限集合A 和B的并的元素数目。显然有

定理:

A ? B ? A ? B ? A ? B (1)
即具有性质A或B的元素的个数等于具 有性质A和性质B的元素个数

容斥原理 定理:设 A1, A2 ,..., An 是有限集合,则
A ? A2 ? ... ? An 1 ?

?
i ?1 n

n

Ai ? ? ? Ai ? A j
i ?1 j ?i

n

+ ? ? ? Ai ? A j ? Ak ? ...
i=1 j>i k>j n ?1

? ( ?1)

A ? A2 ? ... ? An 1

(4)

容斥原理
A1 ? A2 ? ... ? An ? N ? A1 ? A2 ? ... ? An ?1 ? An ? N ? ? Ai ? ?? Ai ? Aj
i ?1 i ?1 j ?i n n

-??? Ai ? Aj ? Ak ? ...
i=1 j>i k>j n

n

? (?1) A1 ? A2 ? ... ? An (5) 容斥原理指的就是(4)和(5)式。


例4。求不超过120的素数个数。 因 ,故不超过120的合数必 然是2、3、5、7的倍数,而且不超过 120的合数的因子不可能都超过11。 设 为不超过120的数 i 的倍数集, i =2,3,5,7。


?120 ? ?120 ? A2 ? ? ? 60, 3 ? ? A ? 40, 2 ? 3 ? ? ? ? ? ?120 ? ?120 ? A5 ? ? ? 24, 7 ? ? A ? 17, 5 ? 7 ? ? ? ? ? ? 120 ? ?120 ? A2 ? A3 ? ? A ? ? 20, 2 ? A5 ? ? 10 ? ? 12, ? 2?3? ? ? ?120 ? ?120 ? A2 ? A7 ? ? ? 8, 3 ? A5 ? ? A ? 8, 14 ? 15 ? ? ? ? ?



?120 ? ?120 ? A3 ? A7 ? ? A ? ? 5, 5 ? A7 ? ? 35 ? ? 3, ? 21 ? ? ? ? 120 ? A2 ? A3 ? A5 ? ? ? ? 4, ? 2 ? 3? 5 ? ? 120 ? A2 ? A3 ? A7 ? ? ? 2, 2 ? 3? 7 ? ? ? ? 120 ? A2 ? A5 ? A7 ? ? ? 1, 2? 5? 7 ? ? ?


A2 ? A3 ? A5 ? A7 ? 120 ? A2 ? A3 ? A5 ? A7 ? A2 ? A3 ? A2 ? A5 ? A2 ? A7 ? A3 ? A5 ? A3 ? A7 ? A5 ? A7 ? A2 ? A3 ? A5 ? A2 ? A3 ? A7 ? A2 ? A5 ? A7 ? A3 ? A5 ? A7 ? A2 ? A3 ? A5 ? A7



? 120 ? (60 ? 40 ? 24 ? 17) ? (20 ? 12 ? 8 ? 8 ? 5 ? 3) ? (4 ? 2 ? 1 ? 1) ? 27.


注意:27并非就是不超过120的素数 个数,因为这里排除了2,3,5,7着 四个数,又包含了1这个非素数。2, 3,5,7本身是素数。故所求的不超 过 120的素数个数为: 27+4-1=30

向量

? 常用头文件#include<math.h> ? 计算几何中一般来说使用double型比较频

繁,请注意数据类型的选择,该用实数的时 候就用double,而float容易失去精度。 ? 判断double型的x是否为0,应当用x<eps && 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]) ? 某些题目需要经常使用向量运算,因此对于 这类问题最好建立构造类型或者类来表示向 量,并将向量乊间的运算迚行重载 ? 一般需要重载加法,减法,和向量乘法

? struct

point{ //构造点的数据类型,也可 作向量使用 ? double x; ? double y; ? }v1,v2; ? point operator+(point p1,point p2); ? double operator*(point p1,point p2);

? 加法
? γ=α+β=(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]),则三角 形面积为 a[1]-a[0] b[1]-b[0] fabs / 2.0 a[2]-a[0] b[2]-b[0] 注意别忘记取绝对值,这里利用面积是否为 0也可以考察三点共线问题 ? 这个方法求面积比海伦公式或者其他方法要 好

? 由求三角形面积的方

法可以推广求凸多边 形面积 ? 如图,从一固定点出 发,向其他各点引辅 助线,这样就分割成 了若干个三角形,利 A 用上式求出每个三角 形的面积再相加即可。

C B D

E

F

? 整点多边形是指顶点的横纵坐标均为整数
? 由外积导出的面积计算公式可以看出,整点

多边形的面积或为整数,或为整数/2. ? Pick公式:整点多边形的面积=内部整点个 数+边上的整点个数/2 - 1. ? NKOJ 1159: 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)

用高斯消元法 解线性方程组

下面是n元线性方程组的一般形式: a1,1x1+a1,2x2+……+a1,nxn=b1 a2,1x1+a2,2x2+……+a2,nxn=b2 …… an,1x1+an,2x2+……+an,nxn=bn

我们可以把它表示为增广矩阵的形式:

a1,1 a2,1
an,1

a1,2 a2,2
an,2

…… …… …… ……

a1,n a2,n
an,n

b1 b2
bn

2 4 1

-1 2 2

3 5 0

1 4 7

×2 ×0.5

2

-1 4 2.5

3 -1 -1.5

1 2 6.5

×0.625 得出: x3=5.25/(-0.875)=-6 x2=(2-(-1)x3)/4=-1 x1=(1-(-1)x2-3x3)/2=9

2

-1 4

3 -1 -0.875

1 2 5.25

a1,1(1) a2,1(1)
an,1(1)

a1,2 (1) …… a2,2 (1) …… …… an,2 (1) ……

a1,n (1) a2,n (1)
an,n (1)

b1 (1) b2 (1)
bn (1)

注:用上标(k)表示 第k次消元前的状态

第1次消元,第1行的乘数: (i=2,3,…,n) 得到新的增广矩阵: a1,1(1) a1,2 …… a2,2 (2) …… …… an,2 (2) ……
(1)

mi ,1 ?
(1)

ai(,1) 1
( a1,11)

a1,n a2,n (2) an,n (2)

b1 b2 (2)
(1)

ai,j(2)=ai,j(1)-mi,1a1,j(1) bi(2)=bi(1)-mi,1b1(1) (i,j=2,3,…,n)

bn (2)

第k次消元前的增广矩阵: a1,1(1) a1,2 (1) ………… a2,2 (2) ………… ………… 第k步消元 ak,k(k) …… 的主元素 …… an,k(k) …… a1,n (1) a2,n (2) ak,n (k) an,n (k) b1 (1) b2 (2) bk (k) bn (k)

第k步消 元的主行

第k次消元,第k行的乘数: (i=k+1,k+2,…,n)

mi ,k ?

ai(,k ) k
( ak kk) ,

增广矩阵的变化: (i,j=k+1,k+2,…,n)

ai,j(k+1)=ai,j(k) -mi,kak,j(k) bi(k+1)=bi(k) -mi,kbk(k)

最后得到的增广矩阵:

a1,1(1)

a1,2 (1) …… a2,2 (2) …… ……

a1,n (1) b1 (1) a2,n (2) b2 (2)

an,n (n) bn (n)

最终结果的计算:

xi ?

b ? ? ai(,i j) x j
(i ) i j ?i ?1 (i ) i ,i

n

a

前面介绍的消元法都是按照自然顺序,即x1、x2、……、xn的顺序消元 的。有:

mi ,k ?

ai(,k ) k
( ak kk) ,

所以每一次消元的主元素都不能为0。如果按照自然顺序消元的过程中 出现的ak,k(k)=0,那么消元无法继续迚行下去。或者| ak,k(k) |很小,也会严 重影响计算精度。

例如(假设运算过程中使用单精度实数): 10-10 1 1 1 1 2 10-10 1 -1010 1 -1010

解得:x1=0,x2=1 这个解与第二个方程差异很大。究其原因,因为消元过程中第一个方 程所乘的系数过大,使得上式“吃掉”了下式,所以在结果中根本无法体 现下式。 但如果调整一下顺序:

1 10-10

1 1

2 1

1

1 1

2 1

解得:x1=1,x2=1,这个解基本符合原方程 所以每次消元的主元素的绝对值应该尽可能大,使得与主行相乘的乘 数尽可能小。

a1,1(1)

a1,2 (1) ………… a2,2 (2) ………… ………… ak,k(k) …… ……… al,k(k) …… ……… an,k(k) ……

a1,n (1) a2,n (2)
ak,n (k)

b1 (1) b2 (2)
bk (k)

al,n(k)
an,n (k)

bl(k)
bn (k)

迚行第k次消元时,将ak,k与以下各元素(包括ak,k)迚行比较,将其中 的最大者所在行与第k行交换。

如果在消元的过程中,增广矩阵出现这样一行:左侧各未知数的系数 都为0,而右侧的常数项不为0,则意味着方程组无解。

在消元过程中,出现这样一行:各未知数的系数和常数项都为0。这相 当于少了一个方程,也就是接下来的消元过程中,方程的个数少于未知数 的个数,方程要么无解,要么有无数组解。下面讨论对于这样的方程,如 何得到一组解。先看这样一个方程:

4 2 2

2 1 1

3 1 2

9 4 5

4 0 0

2 0 0

3 -0.5 0.5

9 -0.5 0.5

如果继续消元(消第2列),必须保证a2,2≠0,可是第2列中不存在非0 的项。

只能够把第3列的元素作为第2次消元的主元素,迚行消元:

4 0 0

2 0 0

3 -0.5 0.5

9 -0.5 0.5

4 0 0

2 0 0

3 -0.5 0

9 -0.5 0

第2次消元得到的元素全部为0,所以第三行元素已失去意义。x2没有 做过主元素,可随意取值,再迚行回代,得到一组可行解。如令x2=0, x3=1,x1=1.5。 对于一般的线性方程组,先迚行消元,每次消元前找到系数不完全为0 的列,相应的元素作为此次消元的主元素,直至第k次消元时,得到的新元 素全部为0,这时把各未知数分为两种:第k+1列至第n列对应的未知数, 可以将这些未知数随意取值;第1列至第k列对应的未知数,这些未知数的 值在回代过程中确定。

时间复杂度: O(n3) 消元O(n3) 选主元素:O(n2) 回代O(n2) 空间复杂度: O(n2) 增广矩阵O(n2) 如使用全选主元素,还需一个存储列与元素对应信息的表,为O(n)

精度: 由于采用实数运算,另外每一次(第一次除外)消元都要使用以前消 元产生的结果,每一次回代都要使用消元结果和其它回代结果,所以累积 误差比较严重,该方法只能够求得近似解。但是可以根据具体需要迚行相 应改迚。

前面讨论了对于一般线性方程组通过实数运算得到近似解的算法。而 在一些问题中,常常要求精确解,这里讨论一下系数、常数项和解均为整 数的线性方程组的精确解法。 前面是用这种方法消元的:

mi ,k ?

ai(,k ) k
( ak kk) ,

ai,j(k+1)=ai,j(k) -mi,kak,j(k) bi(k+1)=bi(k) -mi,kbk(k)

显然这里迚行的是实数运算。

由于不能够保证ai,k(k)是ak,k(k)的倍数,要想消元,必须使两行分别 乘以一个乘数。

mi , k ? m 'i , k ?

( [ ai(,k ) , a k kk) ] k , ( a k kk) , ( [ ai(,k ) , a k kk) ] k ,

ai,j(k+1)=m’i,kai,j(k) -mi,kak,j(k) bi(k+1)=m’i,kbi(k) -mi,kbk(k)

ai(,k ) k

方程较多时,系数有可能越来越大,到一定程度有可能导致系数越界, 因此要随时对各行化简,即把这一行中所有元素除以这些元素的最大公约 数。 但是,无论如何,这也保证不了不会发生越界,因此这种算法一般适 用于系数、未知数范围较小,未知数个数较少的方程。

? 异或方程组就是形如这个样子的方程组: ? M[0][0]x[0]^M[0][1]x[1]^…^M[0][N-1]x[N-

1]=B[0] M[1][0]x[0]^M[1][1]x[1]^…^M[1][N-1]x[N1]=B[1] … M[N-1][0]x[0]^M[N-1][1]x[1]^…^M[N-1][N1]x[N-1]=B[N-1] ? 其中“^”表示异或(XOR, exclusive or), M[i][j]表示第i个式子中x[j]的系数,是1或者0。 B[i]是第i个方程右端的常数,是1或者0。

? 解这种方程可以套用高斯消元法,只须将原

来的加减操作替换成异或操作就可以了,两 个方程的左边异或乊后,它们的公共项就没 有了。

? 考虑系数矩阵,每行是一个方程,每列是一个

未知数在各个方程中的系数(将第i行的方程的 所有系数状压到一个数a[i]里)。 ? 我们分析一下消元乊后各个方程系数的状况: ? 由于我们每次选择最大的一个a[i],并且找到 它最高位上的1,把其它所有方程(包含当前 行以上的方程)这一位的系数全部消去,也就 是说对于每个方程,它的系数a[i]最高位上的1 所在的那一列,仅有这一个1,其余的都是0。 ? Why???

? 再迚一步,如果方程个数n

足够多的话,那

么消元乊后系数矩阵的每 ? 一行仅有一个1,并且这个1 所在的那一列 也仅有这一个1。

? 例题:从N个数中选出仸意个数,使XOR

和最大 ? 这n 个数看做二迚制数,第i 个数的每一位 都作为第i 个方程的系数(也就是上面的a 数组),然后用上面的方法高斯消元,最后 把消元乊后的a 数组全都xor 起来就是答案。


相关文章:
数论
数论_数学_自然科学_专业资料。2002 题二 最大公约数与最小公倍数问题 (20分...【输入样例】 3 100 【输出样例】 981 2005 年 noip 普及组 循环 (circle....
借助计算机快速解决数论问题
借助计算机快速解决数论问题 一、解数独 引言与问题背景:下面是一道信息学奥赛 NOIP 的提高组复赛题 靶形数独的方格同普通数独一样,在 9 格宽×9 格高的大九宫...
基本数论相关内容
数论 9页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见...NOIP 基本数论相关内容 1.求最大公约数、最小公倍数 求最大公约数、 求最...
noip完整考纲
noip完整考纲_IT/计算机_专业资料。noip需要由本人精心整理,得到的童鞋赚 由本人...数论( 3.数论(一) 数论 素性判断 素性判断 筛选建立素数表 筛选建立素数 ...
必背经典算法
一、数论算法 1.求两数的最大公约数 function gcd(a,b:integer):integer; ...NOIP2001 装箱问题有一个箱子容量为 v(正整数,o≤v≤20000),同时有 n 个...
NOIP模板代码(C++)
NOIP模板代码(C++)_计算机软件及应用_IT/计算机_专业资料。NOIP模板代码,精心整理,包含DP,数论,图论和常用数据结构,以及常用STL容器和库函数。...
Noip常用算法大全
Noip 常用算法大全一、数论算法 1.求两数的最大公约数 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b.a mod b);...
NOI及NOIP需要知道的与自己的心得
NOI及NOIP需要知道的与自己的心得_工学_高等教育_教育专区。1 一、 (搜索)双向...数论 a.欧几里德算法 b.扩展欧几里德算法(ax+by=c 的正整数) c.素数测试...
NOIp06-15题解分析
题+排序轻松过 题 4:两遍 bfs,第一次染色判断是否有解,第二次记录能到达最后一行的点,转换为经典 得线段覆盖问题 noip2009 题 1:字符串模拟 题 2:数论。 ...
noip-c++
noip-c++_学科竞赛_高中教育_教育专区。C++ 数论 noip gcd 与 lcm #include<algorithm> using namespace std; int a=12,b=20; int main(){ cout<<__ C++...
更多相关标签:
初等数论 | 数论四大定理 | 代数数论 | 快速数论变换 | 数论入门 | 数论基础 | 数论概论 | 函数论 |