作者LPH66 ( )
看板Math
标题Re: [中学]请教竞赛试题
时间Thu Oct 22 02:33:59 2020
※ 引述《apom0228 (ㄚ碰)》之铭言：
: 2.设a,b,c为质数,若a^2+b^2+c^2=2019,则a+b+c的最大值与最小值的差?
: → tyz : 第二题我除了暴力土法炼钢之外 还想不到其他解~ 10/21 22:57
其实一个个拆不会很麻烦 (因为数字真的不大)
主要是质因数分解後运用 Brahmagupta–Fibonacci 恒等式:
(a^2+b^2)(c^2+d^2) = (ac+bd)^2 + (ad-bc)^2 = (ac-bd)^2 + (ad+bc)^2
以及平方和定理: 一数是平方和若且唯若它质因数分解中 4k+3 的质因数次方皆为偶数
来逐一检讨
2019 < 2025 = 45^2, 所以从 43 往下试:
2019-43^2 = 2019-1849 = 170 = 10*17 = (1^2+3^2)*(1^2+4^2) = 7^2 + 11^2 (O)
= 1^2 + 13^2 (X)
2019-41^2 = 2019-1681 = 338 = 13*26 = (2^2+3^2)*(1^2+5^2) = 7^2 + 17^2 (O)
= 13^2 + 13^2 (O)
2019-37^2 = 2019-1369 = 650 = 50*13
= (1^2+7^2)*(2^2+3^2) = 11^2 + 23^2 (O)
= 17^2 + 19^2 (O)
= (5^2+5^2)*(2^2+3^2) = 5^2 + 25^2 (X)
2019-31^2 = 2019-961 = 1058 = 2*23*23 = 23^2 + 23^2 (O)
2019-29^2 = 2019-841 = 1178 = 2*19*31, 出现单独 4k+3 质数故 1178 不是平方和
2019-23^2 以下就不用算了, 因为已经有 2019 = 23^2+23^2+31^2 的组合
(以上未写出的分解是会找出重覆的组合的分解, 主要是 2 = 1^2 + 1^2 的关系)
总计这里一共找到了:
2019 = 7^2 + 11^2 + 43^2
= 7^2 + 17^2 + 41^2
= 13^2 + 13^2 + 41^2
= 11^2 + 23^2 + 37^2
= 17^2 + 19^2 + 37^2
= 23^2 + 23^2 + 31^2 一共六组解
所求最大是第六组 77, 最小是第一组 61
====
这样的计算量做为中学竞赛题应该还算可以
其他巧解方面我只想得到用余数筛
但因为 2019 = 2016+3 的关系, 若除数是 2016 的因数几乎不会有明确组合的线索
偏偏不论是平方数的常用除数 3, 4, 8 或质数的常用除数 6, 12 都是 2016 的因数..
我只能由除以 6 知没有 2 和 3, 由除以 5 知没有 5 而已
--
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 106.1.234.196 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1603305241.A.5E7.html
1F：→ apom0228 : 感谢指点 10/22 08:02
※ 编辑: LPH66 (106.1.234.196 台湾), 11/17/2020 20:21:45