大榕树 \ Pascal语言 \ 算法与技巧

数论模型

原文链接：http://www.mydrs.org/program/list.asp?id=225

1 基本概念

质数，因式分解如果a和b除以n的余数相等，我们就说a和b关于模n同余。显然，a-b能被n整除当且仅当a和b关于模n同余。 后面的题目会用到这二者的等价性的。

2 基本问题

1.辗转相除法和裴蜀恒等式很基本的问题。辗转相除法不仅可以用来求两个数a,b的最大公约数d=(a,b)，还可以求得满足 ax+by=d (1) 的整数x和y.(1)称为裴蜀恒等式，十分有用。大家可以注意看看后面的例题。可以证明，整数c能写成ax+by(x,y为整数)的形式当且仅当c是d的倍数。 2.模方程和模方程组我们可以解决这样的问题： ax和b关于模n同余 其实就是说，存在y,使得 ax-b=n*y 也就是ax-ny=b 看出点什么了么？对！用裴蜀恒等式。令(a,n)=d, 那么如果b不是d的倍数，方程显然无解，否则作代换 d=c*m，有： (a div m)*x-(n div m)*y=c 利用辗转相除法即可。程序参见例题。 3.一些结论 1.不超过x的质数的个数大约等于：x/ln(x) 例如不超过100000的质数约有100000/ln100000=8686，和实际情况9592差别并不大。 2.n!约等于sqrt(2*pi*n)*(n/e)^n

作者：SRbGa
来源：OIBH
时间：2001-09-25

上一篇：计算几何浅谈
下一篇：NOI2001-炮兵阵地

大榕树 版权所有 ©1999-2006