数论,是专门研究整数的纯数学的分支,而整数的基本元素是素数(也称质数),所以数论的本质是对素数性质的研究。数论被高斯誉为“数学中的皇冠”。按研究方法来看,数论大致可分为初等数论和高等数论。初等数论是用初等方法研究的数论,它的研究方法本质上说,就是利用整数环的整除性质,主要包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、计算数论等等。

解决数学类问题的思维过程

1、相关公式、定理、原理的应用

2、寻找规律、归纳整理递归与递推关系式

3、按照数学方法构造、二进制转化等技巧性处理

解决数学类问题的注意事项

1、规律准确(小数据手工推算、搜索程序验证)

2、数据类型是否合理、数据范围是否超界(大数据处理)

基本概念

NOIP初赛复习(十)数论算法基础-少儿编程教育网
NOIP初赛复习(十)数论算法基础-少儿编程教育网

最大公约数

问题:给定a,b,计算gcd(a,b)

方法1:枚举法

从min(a,b)到1枚举x,并判断x是否能同时整除a和b,如果可以则输出x退出循环。

方法2:分解质因子,程序如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

方法3:欧几里得算法

定理:gcd(a,b)=gcd(b,a mod b),程序如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

方法4:二进制法,程序如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

最小公倍数

问题:计算n个整数a1,a2,...,an的最小公倍数

分析:两个数a1,a2的最小公倍数lcm(a1,a2)=a1*a2/gcd(a1,a2)

lcm(a1,a2,a3)=lcm(lcm(a1,a2),a3),以此类推,可以先求a1,a2的最小公倍数b1,再求b1与a3的最小公倍数b2,再求b2与a4的最小公倍数b3...,程序如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

扩展欧几里得

裴蜀定理:对任何整数a,b,关于未知数x和y的线性丢番图方程(称为裴蜀等式):ax+by=c,方程有整数解当且仅当c是gcd(a,b)的倍数。裴蜀等式有解时必然有无穷多个解。

如方程99x+78y=6,求解x,y的过程如下表(x=y1,y=x1-[a/b]*y1):

NOIP初赛复习(十)数论算法基础-少儿编程教育网

计算ax+by=c的整数解(x,y),程序如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

欧拉函数

对正整数n,欧拉函数是小于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4,因为1,3,5,7均和8互质。

欧拉函数的计算可以在分解质因子过程中完成。程序如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

素数—素数的判定

问题:判定一个数n是否是素数。

分析:如果n是合数,则一定可以把分解a*b的形式,其中a<=b,a!=1,b!=n,如18=2*9,18=3*6。则有:a*a<=a*b=n  =>  a<=NOIP初赛复习(十)数论算法基础-少儿编程教育网

判断依据:如果2到NOIP初赛复习(十)数论算法基础-少儿编程教育网中有n的约数,则n是合数否则n是素数,另外n=1时做特殊处理。

程序如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

素数—埃氏筛法

问题:找出1~n中的素数,程序如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

素数—欧拉筛法(线性筛法)

以n=50为例的欧拉筛法筛选过程部分如下表:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

注意看上表中筛除的数一列中每个数最多只被筛除过一次。程序如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

费马小定理

假如a是一个整数,p是一个素数,gcd(a,p)=1,那么有:NOIP初赛复习(十)数论算法基础-少儿编程教育网

如p=5,a=3,34=81≡1(mod 5),32046=34*511+2≡32(mod5)≡4(mod 5)

费马小定理应用:p是素数,a,p互质,则:

ab mod p=ab mod p mod p

注意:不代表ax≡1(mod p)中x的最小正整数值是p-1,如p=5,a=4时,x的最小正整数值是2

欧拉定理

若n,a为正整数,且n,a互质,即gcd(n,a)=1,则NOIP初赛复习(十)数论算法基础-少儿编程教育网

如n=10,a=3时,φ(10)=4,34=81≡1(mod 10),32017=34*504+1≡3(mod10)

费马小定理是欧拉定理的特殊情况,因为当n为素数时,φ(n)=n-1

欧拉定理应用:n>1,a,n互质,NOIP初赛复习(十)数论算法基础-少儿编程教育网

威尔逊定理

威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。即:当且仅当p为素数时:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

如p=5时,4!=24≡-1(mod 5)

逆元

对任意n>1,如果gcd(a,n)=1,则方程ax≡b(mod n)对模n有唯一解。如果b=1,则要求的x是a对模n的乘法逆元,记为a-1 mod n。

注意:设p=gcd(a,n),如果p>1,则ax≡b(mod n)对模n的解可能无解也可能不唯一!

把ax≡b(mod n)改写成ax+ny=b的形式,方程要有解必须满足p|b

当不满足p|b时,方程无解,因此当b=1且p>1时,逆元不存在,如4x≡1(mod 6)无解;

当p>1且p|b时,利用扩展欧几里得Extended_Euclid求出ax+ny=b的一个特解(x0,y0),方程的一般解为(x0+k*[n/p)],y0-k*[a/p]),x对模n的解一共有p个,其中最小值x1=(x0mod [n/p]+[n/p])mod [n/p],x2=x1+[n/p],xi=x1+(i-1)*[n/p](1<=i<=p),因此只有当p=1时方程对模n的解是唯一的。

如8x≡4(mod 12)对模12的解有2,5, 8,11四个解,而4x≡2(mod 7)对模7只有一个解为4,5x≡1(mod 7)对模7的解只有x=3,它是5对模7的逆元。

中国剩余定理

如计算被9,8,7除时,余数分别为1,2,3的所有整数x。

分析:根据题意得以下方程组

x≡1(mod 9)    x≡2(mod 8)   x≡3(mod 7)

N=9*8*7,m1=N/9=56,m2=N/8=63,m3=N/7=72

56*t1≡1(mod 9),63*t2≡1(mod 8),72*t3≡1(mod 7)

用扩展欧几里得解出t1=-4,t2=-1,t3=-3

x=1*m1*t1+2*m2*t2+3*m3*t3+9*8*7*k

=504*k-1*56*4-2*63*1-3*72*3

=504k+10(k为任意整数)

中国剩余定理的代码如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网

线性同余方程组

NOIP初赛复习(十)数论算法基础-少儿编程教育网

求解过程如下:

①一开始方程的解表示为x,系数1,常数为0,代入方程1得:5x+6y=2,解得x=-2+6*k

②解完方程1,方程组的解为6x-2,系数为6,常数为-2,把6x-2代入方程2中的x得:

2*(6x-2)+8y=4即12x+8y=8解得x=2+2k,把x=2+2k代入原来的解6x-2中得6(2k+2)-2=12k+10,解12k+10满足方程1和方程2

③把12x+10代入方程3中的x得:4(12x+10)+9y=1即48x+9y=-39,解得x=65+3k,代入12x+10得36k+790,也可以写成36k+790 mod 36=36k+34

④因此,符合方程组的一般解为36k+34,最小的正整数解为34

程序如下:

NOIP初赛复习(十)数论算法基础-少儿编程教育网