您所在位置：主题：一个关于最大公约数和最小公倍数的问题
smoon
[专家分：30] 发布于 2005-10-02 22:41:00
最近本小虾在做题时遇到这样一道：
[color=FF0000]NOI’2001第七届全国青少年信息学（计算机）奥林匹克分区联赛
复赛试题 普及组
题二 最大公约数和最小公倍数问题(20分)
问题描述
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件: 1.P,A是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
样例
输入:x0=3 yo=60
输出:4
说明(不用输出)此时的 P Q 分别为:
3 60
15 12
12 15
60 3
所以:满足条件的所有可能的两个正整数的个数共4种.[/color]
我是这样算的：
program noip2;
var
n,i,k:longint;
x,y,t:longint;
function fj(n:integer):integer;
var
i,t:integer;
begin
t:=0;
for i:=2 to n do
begin
if n mod i=0 then
begin
t:=t+1;
n:=trunc(n/i);
end
else break;
end;
fj:=t;
end; {将一个数因式分解,求它的质因数个数(重复的不算)}
function jc(t:integer):longint;
var
i:integer;
s:longint;
begin
s:=1;
for i:=1 to t do
s:=s*i;
jc:=s;
end; {定义阶乘n!=1*2*3*...*n}
function zh(n,m:integer):integer;
var a,b,c:longint;
begin
a:=jc(n);
b:=jc(m);
c:=jc(n-m);
zh:=trunc(a/(b*c));
end; {定义组合数函数=n!/[m!*(n-m)!]}
begin
readln(x,y);
t:=fj(y)-fj(x);
n:=0;
for i:=0 to t do
n:=n+zh(t,i);
writeln(n);
end.
请各位大虾帮我优化一下，或者有什么更简单更好的算法，请写出来，谢谢！
[color=FF0000]NOI’2001第七届全国青少年信息学（计算机）奥林匹克分区联赛
复赛试题 普及组
题二 最大公约数和最小公倍数问题(20分)
问题描述
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件: 1.P,A是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
样例
输入:x0=3 yo=60
输出:4
说明(不用输出)此时的 P Q 分别为:
3 60
15 12
12 15
60 3
所以:满足条件的所有可能的两个正整数的个数共4种.[/color]
我是这样算的：
program noip2;
var
n,i,k:longint;
x,y,t:longint;
function fj(n:integer):integer;
var
i,t:integer;
begin
t:=0;
for i:=2 to n do
begin
if n mod i=0 then
begin
t:=t+1;
n:=trunc(n/i);
end
else break;
end;
fj:=t;
end; {将一个数因式分解,求它的质因数个数(重复的不算)}
function jc(t:integer):longint;
var
i:integer;
s:longint;
begin
s:=1;
for i:=1 to t do
s:=s*i;
jc:=s;
end; {定义阶乘n!=1*2*3*...*n}
function zh(n,m:integer):integer;
var a,b,c:longint;
begin
a:=jc(n);
b:=jc(m);
c:=jc(n-m);
zh:=trunc(a/(b*c));
end; {定义组合数函数=n!/[m!*(n-m)!]}
begin
readln(x,y);
t:=fj(y)-fj(x);
n:=0;
for i:=0 to t do
n:=n+zh(t,i);
writeln(n);
end.
请各位大虾帮我优化一下，或者有什么更简单更好的算法，请写出来，谢谢！
