最大公约数与最小公倍数问题
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;}