ACM/ICPC数论讲座王侯将相宁有种乎？大牛神牛宁有种乎？何以解忧？唯有AC！向百度学习，向谷歌学习！主要内容素
数及筛选法求素数算术基本定理（整数的唯一素因子分解）欧几里德算法扩展的欧几里德算法(ax+by=gcd(a,b))线性同
余方程中国剩余定理费马小定理欧拉函数与欧拉公式快速幂取模一.素数及筛选法求素数1.实现见模板P272.模板“
高效求小范围素数”中：k=i2，应改为：k=ii3.问题：hdoj1164：Eddy''sr
esearchIhttp://acm.hdu.edu.cn/showproblem.php?pid
=1164poj3048：MaxFactorhttp://acm.pku.edu.cn/Jud
geOnline/problem?id=3048二、算术基本定理【定理】正整数n(n≥2)可以唯一分解成素数乘积，即：n
=。1.详细证明见：《什么是数学：对思想和方法的
基本研究》。2.此定理非常重要，它可以解决数论中很多重要问题。3.注意：如果p是整数n的素因子，则p一定
出现在p1p2…ps中。4.对n进行素因子分解可以改造P27之“单独求欧拉函数”。三、欧几
里德算法1.gcd(a,b)=gcd(b,a%b)2.实现见模板P27四、扩展的欧几里德算法1.目的：求ax
+by=gcd(a,b)2.如果b=0，则ax+0y=gcd(a,0)=a，得:x=1,y=0.
3.显然在欧几里得算法的最后会出现形式gcd(a,0)。4.结合2、3，使用逆推便可解得x和y。5.ax+by=
gcd(a,b)=gcd(b,a%b)=bx''+a%by''=bx''
+(a–[a/b]b)y''=ay''+b(x''–[a/b]
y'')5.ax+by=gcd(a,b)=gcd(b,a%b)=bx''+a%by''
=bx''+(a–[a/b]b)y''=ay''
+b(x''–[a/b]y'')例：令a=99，b=78，执行扩展的欧几里得算法：6.实现见模板P27五、线性
同余方程1.目的：解方程ax≡c(modm)2.补充：a1≡b1(modm)且a2≡b2(m
odm)，则a1±a2≡b1±b2(modm)，
a1a2≡b1b2(modm)。如果gcd(c,m)=1,则由ac≡bc(modm
)，得：a≡b(modm)。五、线性同余方程（续）3.ax≡b(modn)，
则：ax–b=ny,所以：ax–ny=b.又：ax–ny=gcd(a,n)=
d，解是存在的。显然：d|b则上述方程有解，否则无解。设方程ax–ny=gcd(a,n)=d的解为
x=u0,则原方程的解为：x0=bu0/d，不同余解集为：x≡x0+in/d(modn),
i=0,1,2,…,d-14.实现见模板P27五、线性同余方程（续）5.问题：poj1061：青蛙的
约会http://acm.pku.edu.cn/JudgeOnline/problem?id=1061
poj2115：CLooooopshttp://acm.pku.edu.cn/JudgeO
nline/problem?id=2115六、中国剩余定理1.伟大的孙子，《孙子算经》（4世纪、晋朝）2.明朝《算法统
宗》：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。六、中国剩余定理（续）3.中国剩余
定理：设w1,w2,…,wk两两互素，则下面同余方程组：x≡b1(modw1)
x≡b2(modw2)…x≡bk(modwk)在0≤x=w1w2…wk内有唯一解。六、中国剩余定理（续）记Wi=W/wi(1≤i≤k)，因为gcd(Wi,
wi)=1,故有整数yi、xi满足：Wiyi+wixi=1,如果记ei=Wiyi,则有：
0(modwj),j≠i1(modwj),j=
i很明显：e1b1+e2b2+…+ekbk就是方程的一个解。4.实现见模板P27六、中国剩余定理（续
）5.问题poj1006：Biorhythmshttp://acm.pku.edu.cn/J
udgeOnline/problem?id=1006七、费马小定理1.【费马小定理】设p是素数，a是任意整数且a
≡0(modp)，则：ap-1≡1(modp)。2.a≡0(modp)在这里等价于gcd(a,
p)=13.费马小定理是欧拉公式的特殊形式七、费马小定理【定理】令p是素数，假设p整除乘积ab，则p整除a或p整除b
（或者p既整除a也整除b）。【定理】素数整除性质：假设素数p整除乘积a1a2…ar,则p整除a1,a2,…
,ar中至少一个因数。七、费马小定理【定理】设p是素数，a是任何整数且a≡0(modp)，则数：a,2a,3
a,…,(p-1)a(modp)与数：1,2,3,…,(p-1)(modp)相同，尽管它们的次序不
同。由上述定理可得：a2a3a…(p-1)a=123…(p-1)(mo
dp)故有：ap-1(p-1)!=(p-1)!(modp)因为(p-1)!与p互素，所以：ap-1=
1(modp)八、欧拉函数与欧拉公式1.欧拉函数?(m)=|{a|1≤a≤m,gcd(a,m)=1}
|2.如果p是素数，则?(p)=p–1=p(1-1/p)3.欧拉公式：如果gcd(a,m)=1,则：
a?(m)≡1(modm)【断言】令1≤b1,b?(m)a(modm)与数列：b1,b2,…,b?(m)(modm)相同，尽管它们可能次序不
同。八、欧拉函数与欧拉公式4.设p是素数，?(pk)=pk–pk-1=pk(1-1/p)5.如果gcd(m
,n)=1,则?(mn)=?(m)?(n)八、欧拉函数与欧拉公式（续）6.m=
，则：?(m)=?(p1r1)?(p2r2)…?(psrs)
=p1r1(1-1/p1)p2r2(1-1/p2)…psrs(1-1/ps)=p1r1p2
r2psrs(1-1/p1)(1-1/p2)(1-1/ps)=m(1-1/p1)(1-
1/p2)…(1-1/ps)7.欧拉函数的实现见模板P27八、欧拉函数与欧拉公式（续）8.问题：poj2
407：Relativeshttp://acm.pku.edu.cn/JudgeOnline/problem
?id=2407hdoj1286：找新朋友http://acm.hdu.edu.cn/showprobl
em.php?pid=1286poj3090：VisibleLatticePointshttp://
acm.pku.edu.cn/JudgeOnline/problem?id=3090poj2478:FareySe
quencehttp://acm.pku.edu.cn/JudgeOnline/problem?id=2478
九、快速幂取模1.目的：求abmodm2.作用RSA加密3.方法：b表示为二进制4.实现见模板P295.
问题：poj1845：Sumdivhttp://acm.pku.edu.cn/JudgeOnl
ine/problem?id=1845其它题目hdoj1299：DiophantusofAlexandria（丢番图方
程）http://acm.hdu.edu.cn/showproblem.php?pid=1299hdoj1222：W
olfandRabbithttp://acm.hdu.edu.cn/showproblem.php?pid=122
2参考书1.《具体数学》，Knuth2.《数论概论》，JosephH.Silverman,孙智伟somewordstoallofyou练习、练习、再练习！总结、总结、再总结！交流、交流、再交流！IOI国家队论文！《算法导论》！《黑书》！模板！组队？Thankyou013---03103236-21326153-2311521-11333217814-11317899yxd[a/b]ba四、扩展的欧几里德算法ei≡ |
|
