题目描述
输入两个正整数 x0,y0，求出满足下列条件的 P,Q 的个数：
- P,Q 是正整数。
- 要求 P,Q 以 x0 为最大公约数，以 y0 为最小公倍数。
试求：满足条件的所有可能的 P,Q 的个数。
输入格式
一行两个正整数 x0,y0。
输出格式
一行一个数，表示求出满足条件的 P,Q 的个数。
输入输出样例
输入
3 60
输出
4
说明/提示
P,Q 有 4 种：
- 3, 60
- 15, 12
- 12, 15
- 60, 3
【题目来源】
NOIP 2001 普及组第二题
题意分析，首先我们肯定知道最大公约数和最小公倍数的乘积等于2个数的的乘积。
然后我们遍历一遍找到他们2个数，用m*n代表，当他们的最大公约数为n时成立。
具体实现看代码。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int m,n,ans,flag; ll gcd(ll x,ll y)//最大公约数 { if(x%y==0) {return y;} return gcd(y,x%y); } int main() { cin>>n>>m; for(int i=1;i<=sqrt(1ll*m*n);i++) { if((1ll*n*m)%i==0&&gcd(i,(1ll*n*m)/i)==n)//就是找有最大公约数有几个可以产生 { ans++; if(1ll*i*i==1ll*n*m) flag=1; } } cout<<ans*2-flag;//最后乘以二是因为只遍历了一半 return 0; }
