Perfect Cubes
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 12581 Accepted: 6697
Description
For hundreds of years Fermat's Last Theorem, which stated simply that for n > 2 there exist no integers a, b, c > 1 such that a^n = b^n + c^n, has remained elusively unproven. (A recent proof is believed to be correct, though it is still undergoing scrutiny.) It is possible, however, to find integers greater than 1 that satisfy the "perfect cube" equation a^3 = b^3 + c^3 + d^3 (e.g. a quick calculation will show that the equation 12^3 = 6^3 + 8^3 + 10^3 is indeed true). This problem requires that you write a program to find all sets of numbers {a,b,c,d} which satisfy this equation for a <= N.
Input
One integer N (N <= 100).
Output
The output should be listed as shown below, one perfect cube per line, in non-decreasing order of a (i.e. the lines should be sorted by their a values). The values of b, c, and d should also be listed in non-decreasing order on the line itself. There do exist several values of a which can be produced from multiple distinct sets of b, c, and d triples. In these cases, the triples with the smaller b values should be listed first.
Sample Input
24Sample Output
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)Source
Mid-Central USA 1995
問輸入n n<=100 在n之內包括n的范圍內找一個a 使得a的三次方等於bcd三者的三次方的和 如果存在 這樣的a 按照a從小到大輸出 對於a相同的 按照b從小到大輸出
另外 Triple內輸入要遵循不遞減的順序
打表用代碼 內存超出了 MLE ac的打表代碼 在最下面
#include<stdio.h>
#include<set>
using namespace std;
struct haha
{
int b,c,d;
friend bool operator< (struct haha ai,const struct haha bi)
{
return ai.b<bi.b;
}
}temp,q;
int hash[1000000+5];
set<struct haha>ss[1000000+5];
int main()
{
int n,i,j,k;
int b[100];
for(i=1;i<=100;i++) { b[i]=i*i*i; hash[i*i*i]=i;}
for(i=2;i<=100;i++)
for(j=i+1;b[j]+b[i]<=1000000;j++)
{
for(k=j+1;b[i]+b[j]+b[k]<=1000000;k++)
{
int mid;
mid=b[i]+b[j]+b[k];
mid=hash[mid];
if(mid==0) continue;
q.b=i;q.c=j;q.d=k;
ss[mid].insert(q);
}
}
set<struct haha>::iterator it;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
if(!ss[i].empty())
for(it=ss[i].begin();it!=ss[i].end();it++)
printf("Cube = %d, Triple = (%d,%d,%d)\n",i,it->b,it->c,it->d);
}
}
return 0;
}
#include<stdio.h>
#include<set>
using namespace std;
struct haha
{
int b,c,d,id;
}q[100];
int main()
{
q[0].id=6;q[0].b=3;q[0].c=4;q[0].d=5;
q[1].id=12,q[1].b=6,q[1].c=8,q[1].d=10;
q[2].id=18,q[2].b=2,q[2].c=12,q[2].d=16;
q[3].id=18,q[3].b=9,q[3].c=12,q[3].d=15;
q[4].id=19,q[4].b=3,q[4].c=10,q[4].d=18;
q[5].id=20,q[5].b=7,q[5].c=14,q[5].d=17;
q[6].id=24,q[6].b=12,q[6].c=16,q[6].d=20;
q[7].id=25,q[7].b=4,q[7].c=17,q[7].d=22;
q[8].id=27,q[8].b=3,q[8].c=18,q[8].d=24;
q[9].id=28,q[9].b=18,q[9].c=19,q[9].d=21;
q[10].id=29,q[10].b=11,q[10].c=15,q[10].d=27;
q[11].id=30,q[11].b=15,q[11].c=20,q[11].d=25;
q[12].id=36,q[12].b=4,q[12].c=24,q[12].d=32;
q[13].id=36,q[13].b=18,q[13].c=24,q[13].d=30;
q[14].id=38,q[14].b=6,q[14].c=20,q[14].d=36;
q[15].id=40,q[15].b=14,q[15].c=28,q[15].d=34;
q[16].id=41,q[16].b=2,q[16].c=17,q[16].d=40;
q[17].id=41,q[17].b=6,q[17].c=32,q[17].d=33;
q[18].id=42,q[18].b=21,q[18].c=28,q[18].d=35;
q[19].id=44,q[19].b=16,q[19].c=23,q[19].d=41;
q[20].id=45,q[20].b=5,q[20].c=30,q[20].d=40;
q[21].id=46,q[21].b=3,q[21].c=36,q[21].d=37;
q[22].id=46,q[22].b=27,q[22].c=30,q[22].d=37;
q[23].id=48,q[23].b=24,q[23].c=32,q[23].d=40;
q[24].id=50,q[24].b=8,q[24].c=34,q[24].d=44;
q[25].id=53,q[25].b=29,q[25].c=34,q[25].d=44;
q[26].id=54,q[26].b=6,q[26].c=36,q[26].d=48;
q[27].id=54,q[27].b=12,q[27].c=19,q[27].d=53;
q[28].id=54,q[28].b=27,q[28].c=36,q[28].d=45;
q[29].id=56,q[29].b=36,q[29].c=38,q[29].d=42;
q[30].id=57,q[30].b=9,q[30].c=30,q[30].d=54;
q[31].id=58,q[31].b=15,q[31].c=42,q[31].d=49;
q[32].id=58,q[32].b=22,q[32].c=30,q[32].d=54;
q[33].id=60,q[33].b=21,q[33].c=42,q[33].d=51;
q[34].id=60,q[34].b=30,q[34].c=40,q[34].d=50;
q[35].id=63,q[35].b=7,q[35].c=42,q[35].d=56;
q[36].id=66,q[36].b=33,q[36].c=44,q[36].d=55;
q[37].id=67,q[37].b=22,q[37].c=51,q[37].d=54;
q[38].id=69,q[38].b=36,q[38].c=38,q[38].d=61;
q[39].id=70,q[39].b=7,q[39].c=54,q[39].d=57;
q[40].id=71,q[40].b=14,q[40].c=23,q[40].d=70;
q[41].id=72,q[41].b=8,q[41].c=48,q[41].d=64;
q[42].id=72,q[42].b=34,q[42].c=39,q[42].d=65;
q[43].id=72,q[43].b=36,q[43].c=48,q[43].d=60;
q[44].id=75,q[44].b=12,q[44].c=51,q[44].d=66;
q[45].id=75,q[45].b=38,q[45].c=43,q[45].d=66;
q[46].id=76,q[46].b=12,q[46].c=40,q[46].d=72;
q[47].id=76,q[47].b=31,q[47].c=33,q[47].d=72;
q[48].id=78,q[48].b=39,q[48].c=52,q[48].d=65;
q[49].id=80,q[49].b=28,q[49].c=56,q[49].d=68;
q[50].id=81,q[50].b=9,q[50].c=54,q[50].d=72;
q[51].id=81,q[51].b=25,q[51].c=48,q[51].d=74;
q[52].id=82,q[52].b=4,q[52].c=34,q[52].d=80;
q[53].id=82,q[53].b=12,q[53].c=64,q[53].d=66;
q[54].id=82,q[54].b=19,q[54].c=60,q[54].d=69;
q[55].id=84,q[55].b=28,q[55].c=53,q[55].d=75;
q[56].id=84,q[56].b=42,q[56].c=56,q[56].d=70;
q[57].id=84,q[57].b=54,q[57].c=57,q[57].d=63;
q[58].id=85,q[58].b=50,q[58].c=61,q[58].d=64;
q[59].id=87,q[59].b=20,q[59].c=54,q[59].d=79;
q[60].id=87,q[60].b=26,q[60].c=55,q[60].d=78;
q[61].id=87,q[61].b=33,q[61].c=45,q[61].d=81;
q[62].id=87,q[62].b=38,q[62].c=48,q[62].d=79;
q[63].id=88,q[63].b=21,q[63].c=43,q[63].d=84;
q[64].id=88,q[64].b=25,q[64].c=31,q[64].d=86;
q[65].id=88,q[65].b=32,q[65].c=46,q[65].d=82;
q[66].id=89,q[66].b=17,q[66].c=40,q[66].d=86;
q[67].id=90,q[67].b=10,q[67].c=60,q[67].d=80;
q[68].id=90,q[68].b=25,q[68].c=38,q[68].d=87;
q[69].id=90,q[69].b=45,q[69].c=60,q[69].d=75;
q[70].id=90,q[70].b=58,q[70].c=59,q[70].d=69;
q[71].id=92,q[71].b=6,q[71].c=72,q[71].d=74;
q[72].id=92,q[72].b=54,q[72].c=60,q[72].d=74;
q[73].id=93,q[73].b=32,q[73].c=54,q[73].d=85;
q[74].id=95,q[74].b=15,q[74].c=50,q[74].d=90;
q[75].id=96,q[75].b=19,q[75].c=53,q[75].d=90;
q[76].id=96,q[76].b=48,q[76].c=64,q[76].d=80;
q[77].id=97,q[77].b=45,q[77].c=69,q[77].d=79;
q[78].id=99,q[78].b=11,q[78].c=66,q[78].d=88;
q[79].id=100,q[79].b=16,q[79].c=68,q[79].d=88;
q[80].id=100,q[80].b=35,q[80].c=70,q[80].d=85;
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<=80;i++)
if(q[i].id<=n)
{
printf("Cube = %d, Triple = (%d,%d,%d)\n",q[i].id,q[i].b,q[i].c,q[i].d);
}
}
return 0;
}
