POJ 1543 — Perfect Cubes – 关浩博的个人网站

浏览量： 1,311

题目大意

输入一个正整数N (N<=100)，求所有的四元组(a, b, c, d)，满足 a^3 = b^3 + c^3 + d^3，其中a,b,c,d均为正整数且1<b<=c<=d<a<=N.

题目链接

http://poj.org/problem?id=1543

输入

一个正整数N

输出

每行输出一个满足条件的四元组。输出形式为：Cube = a, Triple = (b,c,d)
按照a的值，从小到大依次输出；若a相同则按b的值从小到大依次输出；以此类推。具体参见样例输出。

样例输入

样例输出

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)

问题分析

这个问题并不复杂，只要使用4层循环一一枚举a，b，c，d的值，然后对符合条件的情况进行输出即可。另外，我们注意到这个问题中要求输出顺序是从小到大输出，先以a为标准，若a相同则以b为标准，以此类推。所以在枚举时最外层到最内层分别为a，b，c，d即可。

AC代码

#include <stdio.h>
int main()
{
    int n, a, b, c, d;
    scanf("%d", &n);
    for (a = 3; a <= n; a++)
        for (b = 2; b < a; b++)
            for (c = b; c < a; c++)
                for (d = c; d < a; d++)
                    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;
}

注意事项

1、此题数据比较小，这个代码并没有对枚举进行优化，实际上很多枚举是不必要的。
2、调用函数有开销，此题如果调用pow函数来求立方，很容易超时。

打赏赞