欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CODEVS 1012 最大公约数和最小公倍数问题

程序员文章站 2024-01-12 09:33:40
...

问题来源 http://codevs.cn/problem/1012/

确定以下几点就好做了,很基础的题,但是很多人忘了数论的知识,所以才做不出来

    两个数的乘积等于他们的最大公约数和最小公倍数的乘积(数论知识,忘记了可以自己去看看高数书或者百度)

    上述条件反之则不成立,因此找到乘积=x*y的两个数时,需要验证他们的最大公约数是x

    辗转相除法(欧几里得算法)可以比较简便的获得最大公约数

    最小公倍数一定大于最大公约数

    当两个数的最大公约数是x时,则其中一个数(设为p)的范围区间一定是p∈[x, sqrt(x*y)](p%x=0)。

    注意括号中的 p%x=0 意味着循环不是++,是+=x,这在范围较大时,对减少运算量很有意义

#include<stdio.h>
#include<math.h>

// 辗转相除法
char gcd(int x, int y)
{
    int tmp = 0;
    while(x%y != 0)
    {
        tmp = x%y;
        x=y;
        y=tmp;
    }
    return y;
}

int main()
{
    int x,y,p,q,tmp, cnt=0;
    scanf("%d%d", &x, &y);
    if (x > y)// 较小者一定是最大公约数
    {
        tmp = x;
        x = y;
        y = tmp;
    }
    tmp = x * y;
    for (p=x;p<=sqrt(tmp);p+=x)// p+=x即可,不需要p++
    {
        if (tmp%p == 0 && gcd(p, tmp/p) == x)
        {
            cnt++;
        }
    }
    printf("%d", 2*cnt);
    return 0;
}