/*======================================================================
题目描述
输入二个正整数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
思路：
正常的思维是枚举每一个p，x<=p<=y。对每一个p再枚举每一个q，x<=q<=y。
假如p和q满足gcd(p，q)==x&&lcm(p，q)==y则认为得到了一组p、q，解得个数N加1。
如此往复，直到统计完所有的解的个数即可输出N。
但是这个方法，循环复杂度是10^5*10^5==10^10，这个已经远远超出了10^8这个勉强能接受的范围，所以肯定会超时。
优化的思路：
枚举每一个p，假如y%p==0，则这个p可能是解，但要根据p、x、y算出q再验证现在这一组p、q是否是解。
其中q=y*x/p。然后：如果gcd（p，q）==x&&lcm(p,q)==y，那这一组p、q就是一组解了。
这样的解法，循环只有一重，复杂度是10^5，很容易接受。
========================================================================*/
1 #include<stdio.h>
2 int gcd(int a,int b);//最大公约数
3 int lcm(int a,int b);//最小公倍数
4 int main()
5 {
6 int x,y,p,q;
7 int N=0;
8 scanf("%d%d",&x,&y);
9 for(p=x;p<=y;p++)
10 {
11 if(y%p==0)
12 {
13 q=y/p*x;
14 if(gcd(p,q)==x&&lcm(p,q)==y) N++;
15 }
16 }
17 printf("%d\n",N);
18 return 0;
19 }
20 int gcd(int a,int b)//最大公约数，输入要求a>=b>0
21 {
22 int c;
23 if(b==0) return -1;
24 c=a%b;
25 while(c!=0)
26 {
27 a=b;
28 b=c;
29 c=a%b;
30 }
31 return b;
32 }
33 int lcm(int a,int b)
34 {
35 if(a==0||b==0) return -1;
36 return a*b/gcd(a,b);
37 }
