SSL 2683_YMW的数学题_数论

发布于 2017-08-12  8 次阅读


题目描述

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);
    }
}

 

]]>


「墨泼三千烟火,许你一世迷离」