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;}

UVa 11571 Simple Equations Extreme

相关推荐

Prior-informed optimization of treatment recommendation via bandit algorithms trained on large la...

深入解析NoClassDefFoundError：Jackson版本冲突的精准定位与Maven依赖排除实战

PID控制器参数整定实战：从理论到C程序调试

更多资讯

低压电工证中级怎么考？学历不高也能拿全国通用的省级电工证中级

陆良电工证行业前景与薪资待遇良心建议

陆良电工证怎么转异地？官方回应最全攻略来了

韶关电工证通过率揭秘，含金量高到让你想考第二个

陆良电工证有效期多久考前押题怎么准备

电工作业的防火要求全流程办理指南，电子证书怎么拿更靠谱？

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？