2011-06-14 22:11:15Morris
d860. NOIP2001 2.最大公约数和最小公倍数问题
內容 ：
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数条件: 1.P,A是正整数2.要求P,Q以x0为最大公约数,以y0为最小公倍数.试求:满足条件的所有可能的两个正整数的个数.
輸入說明
：
输入x0,y0。
輸出說明
：
输出满足条件的所有可能的两个正整数的个数。
範例輸入 ：
3 60
範例輸出 ：
4
提示
：
输入:x0=3 yo=60输出:4说明(不用输出)此时的 P Q 分别为: 3 6015 1212 1560 3所以:满足条件的所有可能的两个正整数的个数共4种.
出處
：
/**********************************************************************************/
/* Problem: d860 "NOIP2001 2.最大公约数和最小公倍数问题" from NOIP2001普及组第二题*/
/* Language: C */
/* Result: AC (2ms, 261KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-12 12:55:14 */
/**********************************************************************************/
#include<stdio.h>
#include<math.h>
int gcd(int x, int y) {
int t;
while(x%y) {
t = x, x = y, y = t%y;
}
return y;
}
main() {
int x, y;
while(scanf("%d %d", &x, &y) == 2) {
long long n = x * y;
int a, p, q, Ans = 0;
for(a = x; a <= y; a++) {
if(n%a == 0) {
p = a, q = n /a;
if(gcd(p,q) == x) Ans++;
}
}
printf("%d\n", Ans);
}
return 0;
}