题目链接
洛谷 P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题
思路分析
由于 \(P,Q\) 的最大公约数是 \(x_0\)，不妨令 \(P=ax_0,Q=bx_0\)，其中 \(a,b\in\Z_+\) 且 \(a,b\) 互质，那么 \(P,Q\) 的最小公倍数即为 \(abx_0=y_0\)。所以，要想确定 \(P,Q\)，我们只需确定 \(a,b\) 即可。而由前文分析 \(a,b\in\Z_+\) 且 \(ab=\frac{y_0}{x_0}\)。所以题目转换为求 \(\frac{y_0}{x_0}\) 的互质的正因子有几个，枚举即可。
细节把握
-
如果 \(\frac{y_0}{x_0}\) 不是整数，那么就不存在整数 \(a,b\) 乘积为一分数，输出
0； -
如果 \(x_0=y_0\)，即 \(ab=1\)，那么只能 \(a=b=1\)，符合条件，所以输出
1； -
如果不属于上述两类，那么当 \(a=b=\sqrt{\frac{y_0}{x_0}}\) 时，\(a,b\) 必然不互质，枚举就不需要考虑到了，防止在这上面犯错（若不避免则应平常加 \(2\)，根号加 \(1\)，最后直接输出）。
代码呈现
#include<bits/stdc++.h>
using namespace std;int x,y;int gcd(int a,int b){ return b?gcd(b,a%b):a; }
int main(){scanf("%d%d",&x,&y);if (y%x!=0){ putchar('0');return 0; }int z=y/x,cnt=1;if (z==1){ putchar('1');return 0; }for (int i=2;i*i<z;++i){if (z%i==0 && gcd(i,z/i)==1) ++cnt;}printf("%d",(cnt<<1));return 0;
}