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程序调试

更多资讯

Bun 运行时深度解析：性能原理、迁移实践与工程选型指南

Roo Code 2.2.21：基于预测文件长度的截断写入检测可靠性改进解析

Excel时间差计算全指南：从跨午夜陷阱到工时统计实战

Qt工业软件实战：激光焊接控制系统的PLC通信与权限设计

新手也能上手！盘点2026年实力封神的的AI论文网站

如何用 Beads 把 TOML formula 实例化为 molecule 并执行工作流步骤

今日更新

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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