题目描述

YMW最近迷上了数学，听BPM说，善于思考的孩纸才是好孩纸呢，于是他一边看书，一边开始思考些问题。他看到书上说枚举是最强大的算法，他很不服气，思考片刻，便想出一道题，如果我们有两个正整数a，b，那会有多少对数，满足他们之间的最大公因数是a，最小公倍数是b呢？而你是暴力的最忠实粉丝，你能用枚举进行解决吗？

思路

简单来说，题目要我们求出 a,b 使得 gcd(a,b) 和 lcm(a,b) 为题目给出的数

首先我们知道 $a * b = gcd(a,b) * lcm(a, b)$

现在我们将这个式子变形为 $\frac{a * b}{gcd(a,b)} = lcm(a,b)$

再左右同时除以一个 gcd(a,b) $\frac{a*b}{gcd(a,b) * gcd(a, b)} =\frac{lcm(a, b)}{gcd(a,b)}$

$\frac{a}{gcd(a,b)} * \frac{b}{gcd(a,b)} = \frac{lcm(a,b)}{gcd(a,b)}$

显然 $\frac{a}{gcd(a,b)}$ 和  $\frac{b}{gcd(a,b)}$ 互质 即 $gcd(\frac{a}{gcd(a,b)}, \frac{b}{gcd(a,b)}) = 1$

然后$\frac{lcm(a, b)}{gcd(a,b)}$我们是知道的，那么我们可以从1开始枚举一个数到$\frac{lcm(a, b)}{gcd(a,b)}$

另一个数用除法直接求出，那么如果这两个数互质的话那么就是一种方案

此做法在随机数据下表现得非常优秀~

#include 
int gcd(int a, int b)
{
    if (b == 0) return a;
    else return gcd(b, a % b); 
}
int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        if (m % n != 0)
        {
            printf("0\n");
            continue;
        }        
        int t = m / n, ans = 0;;
        for (int i = 1; i <= t; i++)
        {
            if (t % i == 0)
            {
                if (gcd(i, t / i) == 1)
                {
                    ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
}