游客 注册 | 登录
中文 | En

2344 - 最大公约数和最小公倍数问题

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 125 MB

输入二个正整数x0，y0（2<=x0<100000，2<=y0<=1000000），求出满足下列条件的P，Q的个数。

条件：

1. P，A是正整数；

2. 要求P，Q以x0为最大公约数，以y0为最小公倍数。

试求：

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


题目输入

每个测试文件只包含一组测试数据，每组两个正整数x0和y0（2<=x0<100000，2<=y0<=1000000）。


题目输出

对于每组输入数据，输出满足条件的所有可能的两个正整数的个数。

下面是对样例数据的说明：

输入3 60

此时的P Q分别为:

    3     60

    15   12
    12   15
    60   3

<span>所以，满足条件的所有可能的两个正整数的个数共4种。<br />


<span><br />

输入/输出样例

输入格式

3 60

输出格式

4

C语言解答

#include<stdio.h>

int main()
{
  int x,y,m,i,j,n;
  scanf("%d%d",&x,&y);
  m=x>y?x:y;
  int count=0;
  for(i=2;i<=m;i++)
  {
	  int k=i>x*y/i?x*y/i:i;
	  int h=i>x*y/i?i:x*y/i;
	  for(j=k;j>0;j--)
	  {
	    if((i%j==0)&&(x*y/i%j==0))
			break;
	  }
	  for(n=h;n<=x*y;n++)
	  {
	    if((n%i==0)&&(n%(x*y/i)==0))
			break;
	  }
	  if(j==x&&n==y)
		  count++;
  }
  printf("%d\n",count);
  return 0;
}

C++解答

#include<stdio.h>
int g(int n,int m)
{
	int temp,r;
	if(n<m) 
	{ 
		temp=n; 
		n=m; 
		m=temp; 
	} 
	while(m!=0) 
	{ 
		r=n%m; 
		n=m; 
		m=r; 
	} 
	return n;
}
int main()
{
	int a,b,i,j,count;
	while(scanf("%d%d",&a,&b)!=EOF)
	{
		count=0;
		for(i=a;i<=b;i++)
		{
			for(j=i+1;j<=b;j++)
			{
				if(g(i,j)==a&&i*j/g(i,j)==b)
					count++;
			}
		}
		printf("%d\n",2*count);
	}
	return 0;
}
请先登陆