#include <bits/stdc++.h>
using namespace std;

const int N = 50000;

vector<int> prime, num;
int a, b;
vector<pair<int, int>> s;
bool v[N];

void get_prime(int n) {
    for(int i = 2; i <= n; i ++ ) {
        if(!v[i]) prime.push_back(i); 
        for(int j = 0; j < prime.size() && prime[j] <= n / i; j ++ ) {
            v[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

void dfs(int x, int nums) {
    if(x >= s.size()) {
        num.push_back(nums);
        return;
    }
    for(int i = 0; i <= s[x].second; i ++ ) {
        dfs(x + 1, nums);
        nums *= s[x].first;
    }
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

long long lcm(int a, int b) {
    return a * 1ll * b / gcd(a, b);
}

int main() {
    cin >> a >> b;
    int n = a * b;
    get_prime(n);
    int nums = n;
    for(int i = 0; i < prime.size(); i ++ ) {
        if(nums % prime[i] == 0) {
            int cnt = 0;
            while(nums % prime[i] == 0) {
                cnt ++ ;
                nums /= prime[i];
            }
            s.push_back(make_pair(prime[i], cnt));
        }
    }
    if(nums > 1) s.push_back(make_pair(nums, 1));
    dfs(0, 1);
    int ans = 0;
    for(int i = 0; i < num.size(); i ++ ) {
        int x = num[i], y = n / num[i];
        if(gcd(x, y) == a && lcm(x, y) == b) ans ++ ;
    }
    cout << ans << endl;
    return 0;
}

这题算是有点难度的题目了，对于这题其实就是我们求两个数a，b, 使得a和b的最大公约数是x（题目给的，是已知数）, 使得a和b的最小公倍数是y（题目给的也是已知数） 那我们可以简写一下就有 gcd(a, b) == x, lcm(a, b) == y

由最小公倍数公式可得lca(a, b) = a * b / gcd(a, b)

有gcd(a, b) * lcm(a, b) = a * b

由于gcd(a, b) == x, lcm(a, b) == y

带入可得 x * y == a * b

那么题目要我们求什么就已经是不言而喻了 转换一下题目的意思就是要我们求两个数a, b的乘积等于x，y的乘积满足gcd(a, b) == x, lcm(a, b) == y

由于y是a和b的最小公倍数，那么有y * x|b（整除）,x * y|a

那题目的意思就是让我们去找x*y的约数里面有没有满足gcd(a, b) == x, lcm(a, b) == y这样的

对此我们可以提出两种做法：

1.首先是我们直接暴力枚举 x*y 的所有约数 对于所有的约数我们直接判断上述式子成立不成立即可

时间复杂度$O$($\sqrt{N}$)

2.那如果这题有多组询问的话上面的时间复杂度就不一定可以接受了此时我们可以这么做, 我们可以先预处理一下当前题目给出的所有数据范围的一个质数 int的范围内我们只需要处$50000$的一个范围, 为什么呢

我们可以发现, 由于乘积是一对数, 那么我们只要有了乘积, 和其中一个数就可以求出另一个数，所以对于这十亿的范围我们只要求50000就可以覆盖这个int所有的区间，然后对于给的询问分解质因子

比如2有多少个啊，3有多少个啊，5有多少个啊

对于质因子，然后我们去暴力枚举所有的约数，int最大的范围的约数也只有1600个所以这个范围注定不会很大，所以暴力枚举的时间完全可以接受 然后对于这1600个之内的数我们直接逐个判断就完全ok了

总时间复杂度$O(50000 + 1600 * 询问数量)$

最后贴一下最大公约数和最小公倍数怎么求

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}