当前位置：首页 > news >正文

UVa 386 Perfect Cubes

news 2026/6/4 10:32:36

题目描述

费马大定理指出：对于n>2n > 2n>2，不存在大于111的整数a,b,ca, b, ca,b,c满足an=bn+cna^n = b^n + c^nan=bn+cn。然而，对于立方的情况，我们可以找到满足a3=b3+c3+d3a^3 = b^3 + c^3 + d^3a3=b3+c3+d3的整数解（例如123=63+83+10312^3 = 6^3 + 8^3 + 10^3123=63+83+103）。

本题要求：找出所有满足a3=b3+c3+d3a^3 = b^3 + c^3 + d^3a3=b3+c3+d3且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) ...

题目分析

问题的本质

这是一个整数方程求解问题。需要找出所有满足a3=b3+c3+d3a^3 = b^3 + c^3 + d^3a3=b3+c3+d3的四元组(a,b,c,d)(a, b, c, d)(a,b,c,d)，其中2≤b≤c≤d<a≤2002 \leq b \leq c \leq d < a \leq 2002≤b≤c≤d<a≤200。

算法思路

直接枚举b,c,db, c, db,c,d的三重循环，计算b3+c3+d3b^3 + c^3 + d^3b3+c3+d3，然后检查该值是否为某个整数的立方，且该整数在222到200200200范围内，且大于ddd。

枚举范围

bbb从222到200200200
ccc从bbb到200200200
ddd从ccc到200200200

但注意：aaa必须大于ddd，因此ddd最大只需到199199199。

立方根计算

使用cbrt函数计算立方根，由于浮点精度问题，需检查附近整数。

参考代码

// Perfect Cubes// UVa ID: 386// Verdict: Accepted// Submission Date: 2016-06-26// UVa Run Time: 0.040s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structcube{inta,b,c,d;booloperator<(cube x)const{if(a!=x.a)returna<x.a;if(b!=x.b)returnb<x.b;if(c!=x.c)returnc<x.c;returnd<x.d;}};intmain(intargc,char*argv[]){vector<cube>cubes;// 枚举 b, c, dfor(intb=2;b<=200;b++)for(intc=b;c<=200;c++)for(intd=c;d<=200;d++){intsum=b*b*b+c*c*c+d*d*d;// 计算立方根（考虑浮点误差）inta=(int)(cbrt(sum)+0.5);// 检查是否满足方程且 a 大于 d 且 a 在范围内if(a*a*a==sum&&a<=200&&a>d)cubes.push_back({a,b,c,d});}// 按 a, b, c, d 排序sort(cubes.begin(),cubes.end());// 输出结果for(autogroup:cubes){cout<<"Cube = "<<group.a<<", Triple = (";cout<<group.b<<","<<group.c<<","<<group.d<<")"<<endl;}return0;}