最大公约数与最小公倍数有关问题

最大公约数与最小公倍数问题
Description

输入二个正整数x0,y0(2≤x0≤100000，2≤y0≤1000000)，求出满足下列条件的P、Q的个数。
条件:1.P、Q是正整数
二要求P、Q以x0为最大公约数，以y0为最小公倍数。
试求，满足条件的所有可能的两个正整数的个数。
[样例]
输入：x0=3 y0=60
输出：4
说明：(不用输出)此时的 P Q 分别为，
3 60
15 12
12 15
60 3
所以，满足条件的所有可能的两个正整数的个数共4种

Input

二个正整数x0,y0

Output

满足条件的P、Q的个数

Sample Input

3　60

Sample Output

４
//初看这个题比较简单,采用枚举就可以搞定,但提交时间总是过不了,汗，最后参考
http://www.cppblog.com/Climber-pI/archive/2010/09/11/126425.html的思想写出第二段代码

#include <stdio.h>

int main()
{
    int x0, y0, i, j, total, temp, a, b;
    scanf("%d%d",&x0, &y0);
    i = x0;
    total = 0;
    /// freopen("output.txt", "w", stdout);
    while(i <= y0)
    {
       for(j = x0; j <= y0; j += x0)
       {
          if(i < j)
          {
            a = j;
            b = i;
          }else
          {
            a = i;
            b = j;
           }
          do{
            temp = a % b;
            a = b;
            b = temp;
          }while(temp);


         if(a == x0 &&  (i * j / a) == y0)
         { //printf("%d %d\n", i, j);
           total++;
          }
       }
       i += x0;
     }
     printf("%d\n", total);
     return 0;
}

#include <stdio.h>
//原理:以x0,y0分别为最大公约数和最大公倍数的数对个数为2^n，n是y0/x0的不同质因子个数.
// 设p q 为所求的的数 则 设 p = a * x0; q = b * x0; 而 
//p * q / x0 = y0;
//则 a * x0 * b * x0 / x0 = y0;
//则 a * b = y0 / x0; (且a b负质)
//现在题意是求 p q的对数,转换下也就是求 a b的对数
//如果 y0 % x0 != 0的话,那就不存在这样的两个正整数
//而2^n得来,我也不知道,呵呵
int main()
{
	int x0, y0, x, n = 0, i = 2;
	scanf("%d%d", &x0, &y0);
	if(y0 % x0 != 0)
	{
		printf("0\n");
		return 0;
	}
	x = y0 / x0;
	while(x != 1)
	{
		while(x % i != 0)
			i++;
		n++;
		while(x % i == 0)
			x /= i;
	}
	printf("%d\n", 1 << n);
	return 0;
}