网址如下：P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

水了道题

学了求最小公倍数和最大公因数的新方法

我对辗转相除法这个东西有所耳闻，但是从来没有用过

所以我只会枚举法求这两个东西

而且两个数的最小公倍数和最大公因数的乘积等于这两个数的乘积，这个也是今天才知道（虽然说想了想确实是这样，但是没指出来就是不知道）

怪我小时候这两个东西没学好

代码如下：

#include<stdio.h>
#include<math.h>
int f_gcd(int a, int b);//求最大公因数
int count, result, num[20];int main(void)
{int x0, y0;scanf("%d%d", &x0, &y0);//求出y0的所有因数，去除不能被x0整除的数for(int i = 1; i < (int)sqrt(y0); i++)if(!(y0 % i)){if(!(i % x0))  num[count++] = i;if(!((y0 / i) % x0))  num[count++] = y0 / i;}//求P，Q的个数for(int i = 0; i < count - 1; i++)for(int j = i + 1; j < count; j++){int gcd = f_gcd(num[i], num[j]);int lcm = num[i] * num[j] / gcd;if(gcd == x0 && lcm == y0)  result += 2;}//输出if(x0 == y0)  printf("1");else  printf("%d", result);return 0;
}
int f_gcd(int a, int b)
{if(a > b)  a ^= b ^= a ^= b;//让a比b小int x = b, y = a;do{int tmp = x % y;x = y, y = tmp;}while(y);return x;
}

注：

只有x0 = y0时，P才能等于Q，这个时候的答案是1