※ 引述《Ryow (哈扣)》之铭言： : 可能还要多算几项才能找到x^n+y^n+z^n的一般式吧 我放弃 O_Q 又是数学课时间啦 XD 这题六年半前在数学版有一个很漂亮 (而且可以推广) 的解答 #1I3wFtCD (Math) (原发问者删文了, 但由这篇回文所留下来的原文可以知道是一模一样的题目 差在发问者问四次方, 这里 (因为一些原因) 是问五次方) 我有试着解释过他的答案 (在 #1I3ySPhw (Math) ) 而这个回答者後来在 #1I4A6Hwc (Math) 有解释过他的做法 这里我就来重新叙述一下他这个很漂亮的答案 XD 那麽以下是防雷页 回答者提到的这个东西称做 Newton's Identities https://en.wikipedia.org/wiki/Newton's_identities 它是将 n 个数的 k 次方和和这 n 个数的基本对称多项式关连起来的关系式 这里用和这题有关的 3 个数来写 3 个数 x y z 的对称多项式有以下这几个: e1 = x+y+z, e2 = xy+yz+zx, e3 = xyz 为了後面延伸起见, e4 以後定为 0 (等下会说为什麽) 如果把 k 次方和也给个名字: p1 = x+y+z, p2 = x^2+y^2+z^2, p3 = x^3+y^3+z^3, ... 那麽 Newton's Identities 就可以写作: 1*e1 = p1 2*e2 = e1*p1 - p2 3*e3 = e2*p1 - e1*p2 + p3 4*e4 = e3*p1 - e2*p2 + e1*p3 - p4 ... (上面这串式子只要对 n 个数做和上面类似的 e_k p_k 定义那式子依然成立) 这式子是怎麽来的呢? 这里以 3 个数为例: 考虑以 x y z 为根的 t 的三次多项式 (t-x)(t-y)(t-z) = 0 它的展开式就是大家熟知的根与系数关系 t^3 - (x+y+z)t^2 + (xy+yz+zx)t - xyz = 0 或者用上面的 e 代号写成 t^3 - e1*t^2 + e2*t - e3 = 0 那因为 x y z 代入成立, 所以有 {x^3 - e1*x^2 + e2*x - e3 = 0 {y^3 - e1*y^2 + e2*y - e3 = 0 {z^3 - e1*z^2 + e2*z - e3 = 0 然後把这三条式子加起来, 看出什麽了吗 XD 加起来的结果可以用 p 代号代换成 p3 - e1*p2 + e2*p1 - e3*3 = 0 把 e3 写到右边去就是上面的第三条式子了 (这就是我在 #1I3ySPhw (Math) 所给出的解释) 其他条式子可以可以对更多个数进行同样的操作导出来 例如四个数 x y z w 可以导出第四条 p4 - e1*p3 + e2*p2 - e3*p1 + e4*4 = 0 而有趣的是, 这个第四条式子若令 w = 0 则有 (x^4+y^4+z^4) - e1*(x^3+y^3+z^3) + e2*(x^2+y^2+z^2) - e3*(x+y+z) = 0 这个关系式也可以用另一种方式导出来: 上面提到 x y z 成立的关系式 t^3 - e1*t^2 + e2*t - e3 = 0 全式乘以 t 变成 t^4 - e1*t^3 + e2*e^2 - e3*t = 0 然後和上面一样, 代入 x y z 之後三式相加, 就得到了四行前的那条关系式了! 这个代法一方面解释了为什麽上面 e_k 在超过 n 之後要定为 0 的理由 另一方面也给出了对 n 个数计算後面的 p 项的递回关系式 可以看到, 如果中间改乘 t 的其他次方的话 会得到对三个数来说的这一系列的关系式: p4 = e1*p3 - e2*p2 + e3*p1 (同时也能看到这其实根本就是把原来的关系式中 p5 = e1*p4 - e2*p3 + e3*p2 p6 = e1*p5 - e2*p4 + e3*p3 e_k = 0 的项给去掉所得到的式子) .... 也就是说, 只要能求出 e1 = x+y+z, e2 = xy+yz+zx, e3 = xyz 的值 那就可以用这个关系式一项一项把後面的项给求出来 那麽回到原题, 要怎麽求这些对称多项式的值呢? 对三个数可能大家还是可以直接平方展开集项 不过这里我们可以再次回到一开始的关系式 e1 = p1 这没问题 2*e2 = e1*p1 - p2 把它写开其实会发现大家跟它应该熟到不行: 2*(xy+yz+zx) = (x+y+z)*(x+y+z) - (x^2+y^2+z^2) 而 3*e3 这条式子上面解释过了, 这个方法也即是一个求出 xyz 的方法 题目的条件 p1 = 1, p2 = 2, p3 = 3 所以 e1 = 1, e2 = (1*1 - 2)/2 = -1/2, e3 = ((-1/2)*1 - 1*2 + 3)/3 = 1/6 因此对这题而言, 递回关系式就是 p_k = 1*p_{k-1} + (1/2)*p_{k-2} + (1/6)*p_{k-3} 於是就能依序求出 p4 = 1*3 + (1/2)*2 + (1/6)*1 = 25/6 p5 = 1*(25/6) + (1/2)*3 + (1/6)*2 = 6 p6 = 1*6 + (1/2)*(25/6) + (1/6)*3 = 103/12 ... 那至於这题为什麽要求五次方? 大概只是因为接下来的数列正好在五次方和有个整数吧 XD 稍微用个软体算了一下, 再後面的项看起来是没有整数了 ==== 常在解递回关系式的人可能会对上面这一大篇感到似曾相识, 这并不是错觉 因为上面这些步骤其实和解递回关系式的方法是正好相反的运算方向: 如果从上面这条递回关系式开始 p_k = 1*p_{k-1} + (1/2)*p_{k-2} + (1/6)*p_{k-3} 列出它的特徵方程 t^3 - t^2 - (1/2)t - 1/6 = 0 解出它的三根 x y z 然後写出 p_k 的通式 a*x^k + b*y^k + c*z^k 再由给定的 p_1 = 1, p_2 = 2, p_3 = 3 求得系数是 a = b = c = 1 从递回式推得通式的底数 而这题 (以及 Newton's Identities) 则是由通式和初始项推得递回式 这两个操作是同一件事的两个不同运算方向 : → charlie1667: 这雇主真黑，居然有负的报酬 12/22 03:16 : → charlie1667: 好我错了，并不能算负数 雇主真会钻法律漏洞 12/22 03:18 那麽就用个推文当做页末防雷页 我个人是觉得这比负的还黑就是了 XD -- LPH [acronym] = Let Program Heal us -- New Uncyclopedian Dictionary, Minmei Publishing Co. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.177.3.123 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1577028834.A.A1E.html ※ 编辑: LPH66 (180.177.3.123 台湾), 12/22/2019 23:36:36 补充和另一个常见演算法的关连 ※ 编辑: LPH66 (180.177.3.123 台湾), 12/23/2019 02:59:17