题目描述

输入二个正整数,求出满足下列条件的P,Q的个数
条件:  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;
}



来源：破壁人五号