求初等数论的基本概念,基本理论和定理等,越全越好,
题目
求初等数论的基本概念,基本理论和定理等,越全越好,
答案
第一章 有关数论的算法
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.熟记并默写以上算法.
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
- (根号27分之八 — 5倍根号3)× 根号6
- 古文中,(定语从句中)主语与谓语之间若出现“而”字,那么“而”字怎么译
- 关于生命的价值的作文
- 打开电视机出现英文 什么原因 tcl的 哪个懂英文的能解释下
- 写名人的一些事情,用功夫不负有心人或虚心使人进步,骄傲使人落后
- 一篮鸡蛋,第一次取出全部的一半多2个,第二次取出余下的一半少2个,篮子里还剩20个,篮子里原来有鸡蛋多少个?
- 一堆书,3本3本的数剩2本,5本5本的数剩3本,7本7本的数剩2本,它至少有几本?
- real 和the real me 有什么区别?都是“真实的我”的意思吗?
- 五年一班40名师生照相合影.每人一张照片,一共需要付多少钱?合影价格表,定价27.5元含5张照片,加印一张2.5元
- 取12g石灰石(主要成分是CaCO3,杂质不参加反应)放入烧杯中,向其中加入100g一定质量分数的稀盐酸,二者恰好完全反应.反应结束后,称量烧杯中剩余物质的总质量为107.6g(不包括烧杯的
热门考点