题目

求初等数论的基本概念,基本理论和定理等,越全越好,

提问时间：2021-02-18

答案

第一章 有关数论的算法
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])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]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.熟记并默写以上算法.