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

题目描述

输入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;
}