题目描述
输入两个正整数 x_0, y_0x0?,y0?，求出满足下列条件的 P, QP,Q 的个数：
-
P,QP,Q 是正整数。
-
要求 P, QP,Q 以 x_0x0? 为最大公约数，以 y_0y0? 为最小公倍数。
试求：满足条件的所有可能的 P, QP,Q 的个数。
输入格式
一行两个正整数 x_0, y_0x0?,y0?。
输出格式
一行一个数，表示求出满足条件的 P, QP,Q 的个数。
输入输出样例
输入 #1复制
3 60
输出 #1复制
4
说明/提示
P,QP,Q 有 44 种：
- 3, 603,60。
- 15, 1215,12。
- 12, 1512,15。
- 60, 360,3。
对于 100\%100% 的数据，2 \le x_0, y_0 \le {10}^52≤x0?,y0?≤105。
【题目来源】
NOIP 2001 普及组第二题
这道题运用了求最大公约数gcd()函数。（本题的最大特色）
首先大家会发现一个规律，最大公约数乘最小公倍数等于两个正整数x。，y。的乘积。
代码一：
大家会在已知的这两个数中去寻找符合条件的p,q。
因为乘积固定，所以我们只要借助gcd函数去找到符合判断条件的值即可。
因为这个代码采取了一个一个去搜索，结果超时了。
#include<bits/stdc++.h>
using namespace std;int main()
{int m,n;scanf("%d%d",&m,&n);int max,min;if(m>n){max=m;min=n;}else{max=n;min=m;}int i,j,k=0;for(i=min;i<=max;i++){for(j=max;j>=min;j--){if(i*j==m*n){if(__gcd(i,j)==m){k++;}}}}printf("%d",k);return 0;
}
代码二： 基于以上的思路，采取以下修改。
两个循环超时，我们就才用一个循环，对已知的规律进行变形应用，另一个数我们不去找它，就用不变的乘积除以找到一个符合条件的值（因为他们乘积不变，所以彼此有对应关系）。这样可以大大缩短运行时间。
#include<bits/stdc++.h>
using namespace std;int main()
{int m,n;scanf("%d%d",&m,&n);int max,min;if(m>n){max=m;min=n;}else{max=n;min=m;}int i,k=0;for(i=min;i<=max;i++){if(m*n%i==0){if(__gcd(i,m*n/i)==m){k++;}}}printf("%d",k);return 0;
}