第一章 有关数论的算法
1.1 最大公约数与最小公倍数
1.2 有关素数的算法
1.3 方程ax+by=c的整数解及应用
1.4 求a^b mod n
1.1最大公约数与最小公倍数
1.算法1: 欧几里德算法求a，b的最大公约数
function gcd(a,b:longint):longint;
begin
if b=0 then gcdd:=a
else gcd:=gcd(b,a mod b);
end;
2.算法2:最小公倍数acm=a*b div gcd(a,b);
3.算法3:扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y
function exgcd(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:=exgcd(b,a mod b,x,y);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
end;
（理论依据：gcd(a,b)=ax+by=bx1+(a mod b)y1=bx1+(a-(a div b)*b)y1=ay1+b(x1-(a div b)*y1))
1. 2有关素数的算法
1.算法4:求前n个素数:
program BasicMath_Prime;
const
maxn=1000;
var
pnum,n:longint;
p:array[1..maxn] of longint;
function IsPrime(x:longint):boolean;
var i:integer;
begin
for i:=1 to pnum do
if sqr(p[i])<=x then
begin
if x mod p[i]=0 then
begin
IsPrime:=false;
exit;
end;
end
else
begin
IsPrime:=true;
exit;
end;
IsPrime:=true;
end;
procedure main;
var x:longint;
begin
pnum:=0;
x:=1;
while(pnum<n) do
begin
inc(x);
if IsPrime(x) then
begin
inc(pnum);
p[pnum]:=x;
end;
end;
end;
procedure out;
var i,t:integer;
begin
for i:=1 to n do
begin
write(p[i]:5);t:=t+1;
if t mod 10=0 then writeln;
end;
end;
begin
readln(n);
main;
out;
end.
2.算法5:求不大于n的所有素数
program sushu3;
const maxn=10000;
var
i,k,n:integer;
a:array[1..maxn] of integer;
begin
readln(n);
for i:=1 to n do a[i]:=i;
a[1]:=0;
i:=2;
while i<n do
begin
k:=2*i;
while k<=n do
begin
a[k]:=0;
k:=k+i;
end;
i:=i+1;
while (a[i]=0) and (i<n) do i:=i+1;
end;
k:=0;
for i:=1 to n do
if a[i]<>0 then
begin
write(a[i]:5); k:=k+1;
if k mod 10 =0 then writeln;
end
end.
3.算法6:将整数分解质因数的积
program BasicMath_PolynomialFactors;
const
maxp=1000;
var
pnum,n:longint;
num,p:array[1..maxp] of longint;
procedure main;
var x:longint;
begin
fillchar(num,sizeof(num),0);
fillchar(p,sizeof(p),0);
pnum:=0;
x:=1;
while(n>1) do
begin
inc(x);
if n mod x=0 then
begin
inc(pnum);
p[pnum]:=x;
while(n mod x=0) do
begin
n:=n div x;
inc(num[pnum]);
end;
end;
end;
end;
procedure out;
var j,i:integer;
begin
for i:=1 to pnum do
for j:=1 to num[i] do
write(p[i]:5);
writeln;
end;
begin
main;
out;
end.
1.3方程ax+by=c的整数解及应用
1.算法7：求方程ax+by=c的整数解
procedure equation(a,b,c:longint;var x0,y0:longint);
var d,x,y:longint;
begin
d:=exgcd(a,b,x,y);
if c mod d>0 then
begin
writeln('no answer');
halt;
end else
begin
x0:=x*(c div d);
y0:=y*(c div d);
end;
end;
2.方程ax+by=c整数解的应用
例1：有三个分别装有a升水、b升水和c升水的量筒(gcd(a，b)＝1，c>b>a>0),现c筒装满水，
问能否在c筒个量出d升水(c>d>0)。若能，请列出一种方案。
算法分析：
量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：
1.总有一个筒中的水没有变动；
2．不是一个筒被倒满就是另一个筒被倒光；
3．c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其
它限制。
程序如下:
program mw;
type
node=array[0..1] of longint;
var
a,b,c:node;
d,step,x,y:longint;
function exgcd(a,b:longint;var x,y:longint):longint;
var t:longint;
begin
if b=0 then
begin
exgcd:=a;;x:=1;y:=0;
end
else
begin
exgcd:=exgcd(b,a mod b,x,y);
t:=x;x:=y;y:=t-(a div b)*y
end;
end;
procedure equation(a,b,c:longint;var x0,y0:longint);
var d,x,y:longint;
begin
d:=exgcd(a,b,x,y);
if c mod d>0 then
begin
writeln('no answer');
halt;
end else
begin
x0:=x*(c div d);
y0:=y*(c div d);
end;
end;
procedure fill(var a,b:node);
var t:longint;
begin
if a[1]<b[0]-b[1] then t:=a[1]
else t:=b[0]-b[1];
a[1]:=a[1]-t;
b[1]:=b[1]+t
end;
begin
write('a,b,c,d=');
readln(a[0],b[0],c[0],d);
equation(a[0],b[0],d,x,y);
step:=0;
a[1]:=0;b[1]:=0;c[1]:=c[0];
writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
if x>0 then
repeat
if a[1]=0 then fill(c,a) else
if b[1]=b[0] then fill(b,c) else fill(a,b);
inc(step);
writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
until c[1]=d
else
repeat
if b[1]=0 then fill(c,b) else
if a[1]=a[0] then fill(a,c) else fill(b,a);
inc(step);
writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
until c[1]=d;
end.
1.4 求a^b mod n
1.算法8:直接叠代法求a^b mod n
function f(a,b,n:longint): longint;
var d,i:longint;
begin
d:=a;
for i:=2 to b do d:=d mod n*a;
d:=d mod n;
f:=d;
end;
2.算法9:加速叠代法
function f(a,b,n:longint):longint;
var d,t:longint;
begin
d:=1;t:=a;
while b>0 do
begin
if t=1 then begin
f:=d;exit end ;
if b mod 2 =1 then d:=d*t mod n;
b:=b div 2;
t:=t*t mod n;
end;
f:=d
end;
练习：
1.熟记并默写以上算法.
温馨提示：答案为网友推荐，仅供参考