题解 | 最大公约数和最小-NOIP2001普及组复赛B题
B-最大公约数和最小公倍数问题_NOIP2001普及组复赛
https://ac.nowcoder.com/acm/contest/229/B
题目描述
输入二个正整数)
,求出满足下列条件的P,Q的个数
条件: 1.P,A是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
条件: 1.P,A是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
输入描述:
2个正整数
输出描述:
1个数，表示求出满足条件的P,Q的个数
示例1
输入
3 60
输出
4
解答
首先当然是分解质因数了——
map<int,int>xys,yys;//<底数，指数>
for(int i=2;i<=sqrt(x);i++){
while(x%i==0){
x/=i;
xys[i]++;
}
}
if(x!=1)xys[x]++;
for(int i=2;i<=sqrt(y);i++){
while(y%i==0){
y/=i;
yys[i]++;
}
}
if(y!=1)yys[y]++; 下面开始看质因数了
要是的某个因数的指数比
的还大，肯定不可能，直接为0；
要是的某个因数的指数比
的小，代表两个数这个因数指数分别为
的这个因数的指数和
的这个因数的指数——这个因数的指数有两种情况；
要是的某个因数的指数与
的相等，代表两个数这个因数指数均为
的这个因数的指数，一种情况。
以样例为例：
3：
| 底数 | 指数 |
|---|---|
| 3 | 1 |
60:
| 底数 | 指数 |
|---|---|
| 2 | 1 |
| 3 | 1 |
| 5 | 1 |
底数为2,1>0，答案（乘法原理）
底数为3,1=1，答案不变
底数为5,1>0，答案
答案为4
但是！假如有y0指数为0但x0指数非零的数，会判断漏！！！例如：3 5
于是我一开始就
if(y%x){
cout<<0;
return 0;
} 下面是完整源码： #include<bits/stdc++.h>
using namespace std;
int main(){
int x,y,ans=1;
cin>>x>>y;
if(y%x){//最大公约数一定是最小公倍数的约数
cout<<0;
return 0;
}
map<int,int>xys,yys;//<底数，指数>
//分解x0
for(int i=2;i<=sqrt(x);i++){
while(x%i==0){
x/=i;
xys[i]++;
}
}
if(x!=1)xys[x]++;
//分解y0
for(int i=2;i<=sqrt(y);i++){
while(y%i==0){
y/=i;
yys[i]++;
}
}
if(y!=1)yys[y]++;
for(map<int,int>::iterator i=yys.begin();i!=yys.end();++i){
if(xys[i->first]>i->second)ans=0;//这句其实可以不要
if(xys[i->first]<i->second)ans*=2;
}
cout<<ans;
return 0;
} 
京东工作强度 209人发布
