最大公约数和最小公倍数问题

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

条件:
　　1.P,Q 是正整数
　　2.要求P,Q以x为最大公约数,以y为最小公倍数
试求:满足条件的所有可能的2个正整数的个数

这道题我第一眼看就想到用两个循环暴力枚举P，Q，再用辗转相除法求出为最大公约数，再通过最大公约数求出最小公倍数，看是否与x，y相等

 1 #include<iostream>
 2 using namespace std;
 3 int gcd(int a,int b)//最大公约数递归函数 
 4 {
 5 　　if(b==0)return a;
 6 　　return gcd(b,a%b);
 7 }
 8 int main()
 9 {
10 　　int x,y,ans=0;
11 　　cin>>x>>y;
12 　　for(int i=x;i<=y;i++)//暴力枚举P,Q 
13 　　　　for(int j=x;j<=y;j++)
14 　　　　　　if(gcd(i,j)==x && i*j/gcd(i,j)==y)//求最大公约数,推出最小公倍数 
15 　　　　　　　　ans++; 
16 　　cout<<ans;
17 }

但是只能得七八十分，会超时两三个

后来我想到两个数的积等于最大公约数和最小公倍数的积

于是又写了一个

 1 #include<iostream>
 2 using namespace std;
 3 int gcd(int a,int b)//最大公约数递归函数 
 4 {
 5 　　if(b==0)return a;
 6 　　return gcd(b,a%b);
 7 }
 8 int main()
 9 {
10 　　int x,y,ans=0;
11 　　cin>>x>>y;
12 　　for(int i=x;i<=y;i++)//枚举P
13 　　　　if(x*y%i==0 && gcd(i,x*y/i)==x)//Q==x*y/i，判断Q是否存在和最大公约数
14 　　　　　　ans++
15 　　cout<<ans;
16 }

这个程序写到一半我才发现并不是i*j=x*y的i，j都以x为最大公约数，y为最小公倍数

例如4*45=3*60　　5*36=3*60

　　5*16=4*20　　10*8=4*20

所以还是要判断一次最大公约数