P1029 最大公约数和最小公倍数问题
题目描述
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件:
1.P,Q是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
输入输出格式
输入格式：
二个正整数x0,y0
输出格式：
一个数，表示求出满足条件的P,Q的个数
输入输出样例
输入样例#1：
3 60
输出样例#1：
4
说明
P,Q有4种
3 60 15 12 12 15 60 3
本题一个比较重要的等式：a * b / gcd(a, b) = lcm(a, b)
尤次，仅需枚举a，可求得b，然后判断gcd(a, b)是否为x0，同时由于精度问题，还应考虑求的b是否正确
a的枚举：仅需枚举x0的倍数即可，同时应该小于等于y0的两倍，十分显然，
#include <bits/stdc++.h>
const int INF = 0x3f3f3f3f;
inline int min(int a,int b){return a > b? b : a;}
inline int max(int a,int b){return a < b? b : a;}
inline int read(long long &x){
x = ;char ch = getchar();char c = ch;
while(ch > '' || ch < '')c = ch, ch = getchar();
while(ch <= '' && ch >= '')x = x * + ch - '',ch = getchar();
if(c == '-') x = -x;
}
long long gcd(long long a, long long b)
{
long long tmp;
while(b > )
{
tmp = a % b;
a = b;
b = tmp;
}
return a;
} long long x,y,k,j;
int ans;
int main(){
read(x);read(y);
k = x * y;
y >>= ;
for(long long i = x;i <= y;i +=x)
{
j = k / i;
if(i > j)break;
if(j * i == k && gcd(i, j) == x)ans ++;
}
printf("%d", ans << );
return ;
}