pascal 求最大公约数和最小公倍数
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:综合作业 时间:2024/04/29 13:16:23
pascal 求最大公约数和最小公倍数
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.算法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))
pascal求最小公倍数和最大公约数
pascal 求最大公约数和最小公倍数
Pascal语言求两个数的最小公倍数和最大公约数
pascal语言 求n个自然数的最大公约数和最小公倍数
free pascal 求最大公约数与最小公倍数
最大公约数和最小公倍数问题pascal最优
求最大公约数和最小公倍数
求两个自然数,其和是667,最小公倍数与最大公约数之比是120:1(pascal)
pascal最大公约数及最小公倍数问题
pascal 输入任意两个自然数M和N,求两个自然数M和N的最大公约数和最小公倍数
pascal 输入任意两个自然数M和N,求两个自然数M和N的最大公约数和最小公倍数?
求质数最大公约数和最小公倍数