首页 > 代码库 > 2001最大公约数和最小公约数问题
2001最大公约数和最小公约数问题
题目描述 Description
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件: 1.P,Q是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
输入描述 Input Description
二个正整数x0,y0
输出描述 Output Description
满足条件的所有可能的两个正整数的个数
样例输入 Sample Input
3 60
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
题解：
数论+枚举。
公式1：两个数的最小公倍数*最大公约数=两个数的积。
公式2：最大公约数gcd（a，b）=gcd（b，a%b）。
var x,y,j,k,ans:int64;
i:longint;
function gcd(x,y:int64):int64;
begin
if y=0 then exit(x)
else exit(gcd(y,x mod y));
end;
begin
readln(x,y);
for i:=x to y do
begin
j:=x*y div i;
k:=gcd(i,j);
if (k=x)and(i*j div k=y) then inc(ans);
end;
write(ans);
end.
2001最大公约数和最小公约数问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。