[数据结构与算法]“最大公因数和最小公倍数问题”解题思路

代码：

?
#include <bits/stdc++.h> 
using namespace std;
int g(int x,int y){
    if(y == 0){
        return x;
    }
    return g(y,x%y);
}
int main(){
	int x,y,s = 0;
	cin >> x >> y; 
	for(int i = x;i*i <= x * y;i+=x){
	    if(y %(i / x) == 0){
	        if(g(i,y / (i / x)) == x){
	           s += 2; 
	        }
	    }
	}
	cout << s << endl;
	return 0;
}

?

题解：这个题是给我们P和Q的最大公因数和最小公倍数，让我们反推回去，找出最小公因数是x而且最大公倍数为y的P和Q。前几行是一个自定义的函数，用来判断最大公因数。

int g(int x,int y){
    if(y == 0){
        return x;
    }
    return g(y,x%y);
}

主函数中的for循环尽可能地减少时间复杂度，

for(int i = x;i*i <= x * y;i+=x)

循环中的第一个判断用来检查（i / x）是不是y的公因数之一，

而第二个循环调用之前的函数找出 i 和 y /（i /?x）的最小公因数是否等于x（因为是反推）。最后加二说明加了一组P和Q。

易错：

不要把y== 0写成y=0

for循环要尽量节省时间复杂度