UVa 11571 Simple Equations Extreme

题目描述给定三个不同的整数xxx、yyy、zzz满足以下三个方程xyzA x y z AxyzAxyzB xyz BxyzBx2y2z2C x^2 y^2 z^2 Cx2y2z2C输入NNNN250N 250N250个测试用例每个测试用例给出AAA、BBB、CCC1≤A,B,C≤6×10181 \leq A, B, C \leq 6 \times 10^{18}1≤A,B,C≤6×1018要求输出对应的xxx、yyy、zzz。如果存在多组解选择xxx最小的若xxx相同选择yyy最小的。若无解输出No solution.。题目分析这是一道求解三元三次方程组的题目。直接求解整数解在数值范围极大的情况下非常困难。然而我们可以利用三次方程的韦达定理将问题转化为求解一元三次方程的根。代数变换由已知条件xyzA x y z AxyzAx2y2z2C x^2 y^2 z^2 Cx2y2z2C可推导出xyyzzxA2−C2 xy yz zx \frac{A^2 - C}{2}xyyzzx2A2−C​设PA2−C2P \frac{A^2 - C}{2}P2A2−C​则xxx、yyy、zzz是以下一元三次方程的三个根t3−At2Pt−B0 t^3 - A t^2 P t - B 0t3−At2Pt−B0根的分布对于一元三次方程t3ptq0t^3 pt q 0t3ptq0通过平移消去二次项其判别式为Δ(q2)2(p3)3 \Delta \left(\frac{q}{2}\right)^2 \left(\frac{p}{3}\right)^3Δ(2q​)2(3p​)3当Δ0\Delta 0Δ0时方程有三个不同的实根。在本题中三个实根恰好对应三个整数解。通过计算可得三个根的分布区间为aA−2D3,bA2D3 a \frac{A - \sqrt{2D}}{3}, \quad b \frac{A \sqrt{2D}}{3}a3A−2D​​,b3A2D​​其中D3C−A22D \frac{3C - A^2}{2}D23C−A2​且D≥0D \ge 0D≥0是存在实根的必要条件。三个根分别位于以下区间第111个根x1x_1x1​在(−∞,a](-\infty, a](−∞,a]第222个根x2x_2x2​在[a,b][a, b][a,b]第333个根x3x_3x3​在[b,∞)[b, \infty)[b,∞)代码实现// Simple Equations Extreme// UVa ID: 11571// Verdict: Accepted// Submission Date: 2026-06-03// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;typedeflonglongll;ll A,B,C;// 计算 f(t) t^3 - A*t^2 (A^2-C)/2 * t - Blongdoublef(longdoublet){returnt*t*t-A*t*t(1.0l*A*A-C)*t*0.5l-B;}// 在区间 [lo, hi] 内二分求根// sig 1 时找 f(t) 0 的部分sig -1 时找 f(t) 0 的部分longdoublesolve(longdoublelo,longdoublehi,intsig){for(inti0;i200;i){longdoublemid(lohi)*0.5l;if((f(mid)0)(sig0))lomid;elsehimid;}returnlo;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;cinN;while(N--){cinABC;// 剪枝3C 明显小于 A^2 时无实根if(3.0l*C0.9l*A*A){coutNo solution.\n;continue;}// 计算三个根所在的区间端点longdoubleDmax((3.0l*C-1.0l*A*A)*0.5l,0.0l);longdoublea(A-sqrtl(D))/3.0l;longdoubleb(Asqrtl(D))/3.0l;// 分别在三个区间内求根ll x1llround(solve(-1e20l,a,1));ll x2llround(solve(a,b,-1));ll x3llround(solve(b,1e20l,1));// 验证整数解必须严格递增三个不同整数if(x1x2x3Ax1*x2*x3Bx1*x1x2*x2x3*x3Cx1x2x2x3)coutx1 x2 x3\n;elsecoutNo solution.\n;}return0;}