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