最大公约数和最小公倍数问题
题目描述
输入2个正整数x0，y0（2<=x0<100000，2<=y0<=1000000），求出满足下列条件的P，Q的个数。
条件：
1. P，Q是正整数；
2. 要求P，Q以x0为最大公约数，以y0为最小公倍数。
试求：
满足条件的所有可能的两个正整数的个数。
输入
每个测试文件包含不超过5组测试数据，每组两个正整数x0和y0（2<=x0<100000，2<=y0<=1000000）。
输出
对于每组输入数据，输出满足条件的所有可能的两个正整数的个数。
下面是对样例数据的说明：
输入3 60
此时的P Q分别为:
3 60
15 12
12 15
60 3
所以，满足条件的所有可能的两个正整数的个数共4种。
样例输入
3 60
样例输出
4
#include<cstdio>
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)){
count = 0;
for(i = a; i <= b; i++)
{
for(j = i + 1; j <= b; j++)
{
if(g(i, j) == a && i / g(i,j) * j == b)
count++;
}
printf("%d\n", 2 * count);
}
}
return 0;
}
递归法求最小公倍数
#include<iostream>
using namespace std;
int gcd(int n,int m)
{
if(n<m)
{
int temp;
temp=n;
n=m;
m=temp;
}
if(n%m==0) return m;
else return gcd(m,n%m);
}
int main()
{
int a,b,i,j,num;
while(cin>>a&&cin>>b)
{
num=0;
for(i=a;i<=b;i++)
{
for(j=i;j<=b;j++)
{
if(gcd(i,j)==a&&i/gcd(i,j)*j==b) num++;
}
}
cout<<2*num<<endl;
}
return 0;
}
转载于:https://www.cnblogs.com/qing123tian/p/11110915.html
