渴望学到知识的菜鸟


私信TA

用户名:ldhskd

访问量:18395

签 名:

这小伙子人行,能处!

等  级
排  名 140
经  验 6145
参赛次数 1
文章发表 48
年  龄 18
在职情况 学生
学  校
专  业

  自我简介:

解题思路:

这题就是变向地求最小公倍数

因为这样才能 各组平分核桃 


那这个问题就变成了如何求最小公倍数了,那我们应该使用辗转相除法来求


最大公因数和最小公倍数的相关性质:两数的乘积除以最大公因数就是最小公倍数



辗转相除法是古希腊求两个正整数的最大公约数的,也叫欧几里德算法,其方法是用较大的数除以较小的数,上面较小的除数和得出的余数构成新的一对数,继续做上面的除法,直到出现能够整除的两个数,其中较小的数(即除数)就是最大公约数。


如果一个数能够同时整除x和y,则必能同时整除b和y;而能够同时整除b和y的数也必能同时整除x和y,即x和y的公约数与b和y的公约数是相同的,其最大公约数也是相同的,则有f(x, y)= f(y, x%y)(y > 0),如此便可把原问题转化为求两个更小数的最大公约数,直到其中一个数为0,剩下的另外一个数就是两者最大的公约数。





参考代码:

#include <stdio.h>
int gcd(int a, int b)//求最大公约数
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)//求最小公倍数
{
    return a * b / gcd(a, b);
}
int main()
{
    //这题的题目有一点求最小公倍数的味道
    int a, b, c;
    scanf("%d%d%d", &a, &b, & c);
    //先求出a和b的最小公倍数,然后再用a和b的最小公倍数和c求出他们三个之间的最小公倍数
    printf("%d\n",lcm(lcm(a,b),c));
    return 0;
}


 

0.0分

10 人评分

  评论区