首页 > ACM题库 > HDU-杭电 > HDU 1334 Perfect Cubes-分治-[解题报告] C++
2013
12-09

HDU 1334 Perfect Cubes-分治-[解题报告] C++

Perfect Cubes

问题描述 :

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 <= 200.

输出:

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.

The first part of the output is shown here:

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)

Note: The programmer will need to be concerned with an efficient implementation. The official time limit for this problem is 2 minutes, and it is indeed possible to write a solution to this problem which executes in under 2 minutes on a 33 MHz 80386 machine. Due to the distributed nature of the contest in this region, judges have been instructed to make the official time limit at their site the greater of 2 minutes or twice the time taken by the judge’s solution on the machine being used to judge this problem.

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1334

题意:输出所有(1,200]区间上满足a^3==b^3+c^3+d^3的式子。

mark:水题,枚举a、b、c,在[c,a-1]区间上二分求d后验证。n次wa,二分写得挫。

代码:

# include <stdio.h>
# include <math.h>


int sqrt3(int num,int l,int r)
{
    int mid = 210 ;
    if (l*l*l>num) return 0 ;
    if (r*r*r<num) return 210 ;
    while (r-l>1){
        mid = (r+l)/2 ;
        if (mid*mid*mid <= num) l = mid ;
        else r = mid ;
    }
    if (r*r*r==num) return r ;
    return l ;
}


int main ()
{
    int a, b, c, d ;
    for (a = 6 ; a <= 200 ; a++)
        for (b = 2 ; b < a ; b++)
            for (c = b ; b*b*b+c*c*c < a*a*a ; c++)
            {
                d=sqrt3(a*a*a-b*b*b-c*c*c,c,a-1) ;
                if (d<c) break ;
                if (d>=a) continue ;
                if(a*a*a==b*b*b+c*c*c+d*d*d)
                printf ("Cube = %d, Triple = (%d,%d,%d)\n",
                    a,b,c,d) ;
            }
    return 0 ;
}

解题报告转自:http://www.cnblogs.com/lzsz1212/archive/2012/02/16/2353628.html


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  4. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。