1. 题目

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

2. 思想

• 定一个 gcd() 函数，用于取两个数的最大公约数
• 两重for循环遍历，找出合适的值即可
  注意for循环的边界问题，i/j的step可以调成 最大公约数，同时其二者的上界都可以写为 sqrt(x *y)。如果单纯的写成i<=y会导致TLE错误。

其实两重 for 循环的复杂度还是欠妥，可以优化成 O(n)。 => 这类问题都可以简化成，如果两个变量存在关联，那么我们就得考虑是否只要控制其中一个变量即可讨论完成了？

3. 代码

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;

//求a,b的最大公约数 
int gcd(int a,int b){
	int remain = a;
	while(remain){
		remain = a%b;
		a = b;
		b = remain;		
	}
	return a;
}

int main(){
	ll x ,y ;
	cin >> x >> y; //输入两个数
	int res = 0;
	int flag = 0;
	//1.该数的范围一定不会超过最小公倍数y
	
	ll prod = x * y;
	for (int i = x;i<= sqrt(prod);i+=x){ //2.可以修改step
		for (int j = y;j>=sqrt(prod);j-=x){
			int a = gcd(i,j);
			ll b = j*i/a; //求出最大公约数 
			if( a == x && b==y){
				if (i == j) flag = 1;
				res++;
			}			
		}
	} 
	cout << res * 2 - flag ;	
}