最新消息:点击查看大S的省钱秘笈

Vijos P1131 最小公倍数和最大公约数问题

Vijos题解 Slyar 69浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

描述 Description

输入二个正整数x0,y0(2≤x0≤100000,2≤y0≤1000000),求出满足下列条件的P、Q的个数。
条件:
1.P、Q是正整数
2.要求P、Q以xO为最大公约数,以yO为最小公倍数。
试求,满足条件的所有可能的两个正整数的个数。

输入格式 Input Format

两个正整数

输出格式 Output Format

满足条件的所有可能的两个正整数的个数

Tip:我是枚举的,但利用了"两数乘积=最大公约数*最小公倍数"这个公式和碾转相减法求最大公约数,注意检验最大公约数前要先判断两个数是否合理。有更好的方法是寻找两数的质因子数,但是我数学不好,不太理解呵呵~

#include <stdio.h>

int gcd(int a,int b){
while(a!=b){
if(a>b) a=a-b;
if(a<b) b=b-a;
}
return a;
}

int main(){

long total=0,x,y,x0,y0;
scanf("%ld%ld",&x0,&y0);
for (x=2;x<=y0;x++)
if ((x%x0==0)&&(y0%x==0)){
y=x0*y0/x;
if (x0==gcd(x,y)) total++;
}
printf("%ld",total);
system("pause");
return 0;
}

转载请注明:Slyar Home » Vijos P1131 最小公倍数和最大公约数问题

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址