15届蓝桥杯CB组宝石组合公式推导_蓝桥杯第d十五借宝石组合

作者：菜鸟追梦旅行 | 2024-04-26 11:04:55

踩

蓝桥杯第d十五借宝石组合

首先有

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

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

带入原式化简得到

${\frac{\gcd(a,c) \cdot \gcd(b,c)}{\gcd(\text{lcm}(a,b),c)}}$

注意到

$\gcd(lcm(a,b),c)=lcm(gcd(a,c),gcd(b,c))$

从而原式等价于

$gcd(gcd(a,c),gcd(b,c))$

即

$gcd(a,b,c)$

下面证明

$\gcd(lcm(a,b),c)=lcm(gcd(a,c),gcd(b,c))$

$<=>\gcd(a,b,c)\cdot\gcd(ab,c\cdot\gcd(a,b))=\gcd(a,b)\cdot\gcd(b,c)\cdot\gcd(a,c)$

我们只需反复套用式子

$k\cdot gcd(a,b) = gcd(ak,bk)$

不难发现左右均等于

$gcd(aab,aac,abb,abc,acc,bbc,bcc)$

从而得证

随后只需枚举约数就能得到正解

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/490580