UVa 386 Perfect Cubes

题目描述费马大定理指出对于n2n 2n2不存在大于111的整数a,b,ca, b, ca,b,c满足anbncna^n b^n c^nanbncn。然而对于立方的情况我们可以找到满足a3b3c3d3a^3 b^3 c^3 d^3a3b3c3d3的整数解例如123638310312^3 6^3 8^3 10^31236383103。本题要求找出所有满足a3b3c3d3a^3 b^3 c^3 d^3a3b3c3d3且a≤200a \leq 200a≤200的整数解其中b,c,d≥2b, c, d \geq 2b,c,d≥2。输出格式按aaa的非递减顺序输出每行一个解格式为Cube a, Triple (b,c,d)。对于相同的aaa按bbb的非递减顺序输出。bbb、ccc、ddd也应满足b≤c≤db \leq c \leq db≤c≤d。样例输出部分Cube 6, Triple (3,4,5) Cube 12, Triple (6,8,10) Cube 18, Triple (2,12,16) Cube 18, Triple (9,12,15) Cube 19, Triple (3,10,18) Cube 20, Triple (7,14,17) Cube 24, Triple (12,16,20) ...题目分析问题的本质这是一个整数方程求解问题。需要找出所有满足a3b3c3d3a^3 b^3 c^3 d^3a3b3c3d3的四元组(a,b,c,d)(a, b, c, d)(a,b,c,d)其中2≤b≤c≤da≤2002 \leq b \leq c \leq d a \leq 2002≤b≤c≤da≤200。算法思路直接枚举b,c,db, c, db,c,d的三重循环计算b3c3d3b^3 c^3 d^3b3c3d3然后检查该值是否为某个整数的立方且该整数在222到200200200范围内且大于ddd。枚举范围bbb从222到200200200ccc从bbb到200200200ddd从ccc到200200200但注意aaa必须大于ddd因此ddd最大只需到199199199。立方根计算使用cbrt函数计算立方根由于浮点精度问题需检查附近整数。参考代码// Perfect Cubes// UVa ID: 386// Verdict: Accepted// Submission Date: 2016-06-26// UVa Run Time: 0.040s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structcube{inta,b,c,d;booloperator(cube x)const{if(a!x.a)returnax.a;if(b!x.b)returnbx.b;if(c!x.c)returncx.c;returndx.d;}};intmain(intargc,char*argv[]){vectorcubecubes;// 枚举 b, c, dfor(intb2;b200;b)for(intcb;c200;c)for(intdc;d200;d){intsumb*b*bc*c*cd*d*d;// 计算立方根考虑浮点误差inta(int)(cbrt(sum)0.5);// 检查是否满足方程且 a 大于 d 且 a 在范围内if(a*a*asuma200ad)cubes.push_back({a,b,c,d});}// 按 a, b, c, d 排序sort(cubes.begin(),cubes.end());// 输出结果for(autogroup:cubes){coutCube group.a, Triple (;coutgroup.b,group.c,group.d)endl;}return0;}