GCD和LCM
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:33 测试通过:10
描述
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件: 1.P,Q是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
输入
两个数 x0 y0
输出
满足条件的所有可能的两个正整数的个数
样例输入
3 60
样例输出
4
提示
此时的 P Q 分别为:
3 60
15 12
12 15
60 3
所以:满足条件的所有可能的两个正整数的个数共4种.
题目来源
NOIP2001
分析：因为x0*y0==a*b；所以找到他们之间的一个关系，然后只要从小的开始就可以了，判断b是否能被x0整除，但差点忽略的问题是有可能x0不是最小。如6、30所以要判断下，采用欧几里德辗转相除。AC了
 #include <stdio.h>
#include <math.h>
int gcd(int a,int b)
   {
 int c;
if (a<b)
  {
c=a;
a=b;
b=c;
 }
while (a%b)
{
c=a%b;
a=b;
b=c;
}
return b;
 }
int main()
{
int x0,y0,i,j,k,n=0;
scanf("%d%d",&x0,&y0);
for (i=x0;i<=y0;i+=x0)
{
if (x0*y0/i%x0==0)
{
//判断最小公倍数
if (x0*y0%i==0)
{
if(gcd(i,x0*y0/i)==x0)
n++;
}
}
}
printf("%d\n",n);
}
注：代码注释中应为//判断最大公约数。
|