wikioi1012 最大公约数和最小公倍数有关问题（2001年NOIP全国联赛普及组）

wikioi1012 最大公约数和最小公倍数问题（2001年NOIP全国联赛普及组）

题目描述 Description

输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数

条件:  1.P,Q是正整数

2.要求P,Q以x0为最大公约数,以y0为最小公倍数.

试求:满足条件的所有可能的两个正整数的个数.

输入描述 Input Description

二个正整数x0,y0

输出描述 Output Description

满足条件的所有可能的两个正整数的个数

样例输入 Sample Input

3 60

样例输出 Sample Output

4

#include <iostream>#include <cmath>using namespace std;int gcd(int a,int b){  while(b!=0)  {    int o = a%b;    a = b;    b = o;  }  return a;}int main(){  int x,y;  cin >> x >> y;  int v = x*y;  int s = (int)sqrt(v);  int n = 0;  for(int i=x; i<=s; i++)    if((v%i==0)&&(gcd(v/i,i)==x)) n++;  n *= 2;  cout << n;  return 0;}

要点：两个数的乘积等于二者最大公约数和最小公倍数的乘积。