最小公倍数和最大公约数的求法
能不能给一些优化的算法,不用从0-n/2这样的枚举 问题点数：20、回复次数：5Top
1 楼a12345（唯微）回复于 2002-01-06 04:10:04 得分 0
展转相除法
Top
2 楼Arter（阿蒂尔）回复于 2002-01-06 09:24:48 得分 20
http://algorithm.myrice.com/resources/index.html
{============================
数论算法
by starfish
=============================}
{=== 欧几里德算法求a，b的最大公倍数 ===}
function euclid(a,b:longint):longint;
begin
if b=0 then euclid:=a
else eucild:=euclid(b,a mod b);
end;
{=== 扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y ===}
function extended_euclid(a,b:longint;var x,y:longint):longint;
var
t:longint;
begin
if b=0 then
begin
result:=a;
x:=1;
y:=0;
end
else
begin
result:=extended_euclid(b,a mod b,x,y);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
end;
{=== 求解模线性方程 ax ≡ b (mod n) 其中n>0 ===}
procedure modular_linear_equation_solver(a,b,n:longint);
var
d,x,y,e,i:longint;
begin
d:=extended_euclid(a,n,x,y);
if b mod d>0 then
writeln('No answer!') {输出无解信息}
else
begin
e:=x*(b div d)mod n;
for i:=0 to d-1 do
writeln( (e+i*(n div d)) mod n ); {输出第i个解 }
end;
end;
{==================================
求解模线性方程组(中国余数定理):
a ≡ B[1] (mod W[1])
a ≡ B[2] (mod W[2])
..........
a ≡ B[k] (mod W[k])
其中W,B已知，W[i]>0且W[i]与W[j]互质，
求a.
===================================}
function China(var B,W:array[1..k] of longint):longint;
var
i,d,x,y,a,m,n:longint;
begin
n:=1;
for i:=1 to k do
n:=n*W[i];
a:=0;
for i:=1 to k do
begin
m:=n div W[i];
d:=extended_euclid(W[i],m,x,y);
a:=(a+y*m*B[i])mod n;
end;
if a>0 then China:=a
else China:=a+n;
end;
{====================================================
返回x用二进制表示的长度，例如x=1011010，则返回7
====================================================}
function Binary_Length(x:integer):integer;
begin
result:=0;
while x>0 do
begin
inc(result);
x:=x shr 1;
end;
end;
{===============================
模取幂运算
计算a^b mod n
用到的Binary_Length可在前文找到
================================}
function Modular_Exponentiation(a,b,n:integer):integer;
var
c,i:integer;
begin
c:=0;
result:=1;
for i:=Binary_Length(b)-1 downto 0 do
begin
c:=c*2;
result:=(result*result) mod n;
if (b and (1 shl i))>0 then {if b[i]=1 then... }
begin
inc(c);
result:=(result*a) mod n;
end;
end;
end;
{=====================================
Miller-Rabin随机性素数测试算法
说明：
这种算法很快，但是有很小的概率会出错；
对于任意奇数n>2和正整数s,该算法的出错
概率至多为2^(-s)，因此，增大s可以减小
出错概率，一般取s=50就足够了。
=====================================}
{用到的Binary_Length可在前文找到}
function Witness(a,n:integer):boolean;
var
i,d,x:integer;
begin
d:=1;
for i:=Binary_Length(n-1)-1 downto 0 do
begin
x:=d;
d:=(d*d) mod n;
if (d=1)and(x<>1)and(x<>n-1) then begin result:=true;exit;end;
if ((n-1) and (1 shl i))>0 then d:=(d*a) mod n; {if b[i]=1 then... ,其中b[i]是n-1的二进制的第i+1位}
end;
if d<>1 then result:=true
else result:=false;
end;
{ 在调用此函数之前记着要调用 randomize}
function Miller_Rabin(n,s:integer):boolean; {n为待测试的整数,n为素数则返回true;s为出错概率控制参数;}
var
j,a:integer;
begin
for j:=1 to s do
begin
a:=random(n-2)+1;
if Witness(a,n) then begin result:=false; exit;end; {n为合数，可以肯定}
end;
result:=true; {n为素数，只要s足够大，几乎可以肯定}
end;
Top
3 楼Solstice（大佛）回复于 2002-01-06 09:55:57 得分 0
收藏！Top
4 楼nofog（nofog）回复于 2002-01-09 16:56:03 得分 0
markTop
5 楼macbolo（）回复于 2002-01-10 21:39:37 得分 0
最大公约数 两数，大的a除小的b，得余数c，a=b,b=c,直到余数为0，此时的b为最大公约数。
最小公倍数 初始a*初始b/最大公约数 Top
