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

题目描述

输入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
     
      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
     
      using namespace std;int gcd(int n,int m){    if(n
      
       >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<