最大公约数和最小公倍数问题（3月30日）

一

给出xo和yo ，找两个数满足 xo是这两个数的最小公约数，yo是这两个数的最小公倍数。首先题目给的数据是(2<=x0<100000，2<=y0<=1000000) 如果用双层for循环的话一看就会直接超时。

二

对于求最大公约数我们就直接用欧几里得算法，
我们还有一个关系式：
a *b = 最大公约数 X 最小公倍数
所以我们只要求出最大公约数就可以很容易求出最小公倍数。

三

如果直接用双重for就会直接炸掉，(2<=x0<100000，2<=y0<=1000000)数据范围超太多了。但是校OJ的测试点不全且不一定到达数据最坏的情况。

我用双重for循环在校OJ上得80分
洛谷上得50分

当我把for循环改成单个for循环时在校OJ上就过了

这里简写
for(int a = 2;a<=x*y;a++){
			b = x*y/a;
}

但是在洛谷上还有一个测试点超时

我们可以知道 15 12 12 15 是相同的一组但是在遍历的时候我们遍历了两次，对于整体我们一次能遍历两个所以我们可以把遍历的范围缩小到sqrt(x*y)。这样就不会超时了。

但这样在洛谷上交还是过不了，始终90分，我下载了测试点才知道当 x = y 时x == y
无论是最大公约数还是最小公倍数都是1也只有1和1这一组满足 。

所以当x == y 时我们需要特判一下，这样才能圆满AC.

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a,b,x,y,num;

//欧几里得 最小公倍数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

int main(){
	cin>>x>>y;
//这里要特盘
	if(x == y){
		cout<<"1";
		return 0; 
	}
	for(int a = 1;a<=sqrt(x*y);a++){
	//我这里写的答辩，可以简写的
			b = x*y/a;
			int ma = max(a,b);
			int mi = min(a,b);
			int g = gcd(mi,ma%mi);
			int l = (x*y)/g;
			if(g == x&&l == y&&a*b == x*y){
				num++;
			}
	}
	cout<<num*2;
return 0;
}