02810: 完美立方

bruteforce, http://cs101.openjudge.cn/practice/02810

形如 $a^{3} = b^{3} + c^{3} + d^{3}$ 的等式被称为完美立方等式。例如 $12^{3} = 6^{3} + 8^{3} + 10^{3}$ 。编写一个程序，对任给的正整数N (N ≤ 100)，寻找所有的四元组 (a, b, c, d)，使得 $a^{3} = b^{3} + c^{3} + d^{3}$ ，其中 a,b,c,d 大于 1, 小于等于N，且 b ≤ c ≤ d。

输入

一个正整数N (N≤100)。

输出

每行输出一个完美立方。输出格式为： Cube = a, Triple = (b,c,d) 其中a,b,c,d所在位置分别用实际求出四元组值代入。

请按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则b值小的优先输出、仍相同则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)

只对b,c,d循环，用字典。

python

# AC时间: 65ms
n = int(input())
cube = {i**3: i for i in range(2, n+1)}
reversed_cube = {v: k for k, v in cube.items()}
ans = []
for b in range(2, n):
    for c in range(b, n):
        for d in range(c, n):
            if (a := reversed_cube[b]+reversed_cube[c]+reversed_cube[d]) in cube:
                ans.append((cube[a], b, c, d))
ans.sort()
for s in ans:
    print(f"Cube = {s[0]}, Triple = ({s[1]},{s[2]},{s[3]})")

python

import math		# AC时间: 202ms

n = int(input())
# 计算立方值并存储在列表中以避免重复计算
cubes = [i ** 3 for i in range(n + 1)]
ans = []
for b in range(2, n):
    for c in range(b, n):
        for d in range(c, n):
            if (a := cubes[b] + cubes[c] + cubes[d]) in cubes:
                ans.append((round(math.pow(a, 1 / 3)), b, c, d))
ans.sort()
for a, b, c, d in ans:
    print(f"Cube = {a}, Triple = ({b},{c},{d})")

当我们将 functools.lru_cache应用到函数上时，每次调用函数，它都会检查其参数是否已经在缓存中如果在缓存中，它将返回缓存的结果，而不需要重新计算。如果没有在缓存中，那么函数将被调用并且结果将被添加到缓存中。当缓存满了，最少使用的条目将被抛弃。

python

# AC时间: 1352ms
from functools import lru_cache

@lru_cache(maxsize = 128)
def cube(i):
    return i**3

def solv():
    N = int(input())
    ans = []
    for a in range(2,N+1):
        for b in range(2,a):
            for c in range(b,a):
                for d in range(c,a):
                    #if a ** 3 == b ** 3 + c ** 3 + d ** 3:
                    if cube(a) == cube(b) + cube(c) + cube(d):
                        #print('Cube = %d, Triple = (%d,%d,%d)' %(a,b,c,d))
                        ans.append((a,b,c,d))
    
    return ans

for a,b,c,d in solv():
    print(f"Cube = {a}, Triple = ({b},{c},{d})")

python

# AC时间:875ms
n = int(input())
cube = [i**3 for i in range(n+1)]
for a in range(3,n+1):
    for b in range(2,a):
        for c in range(b,a):
            for d in range(c,a):
                if cube[a]==cube[b]+cube[c]+cube[d]:
                    print(f"Cube = {a}, Triple = ({b},{c},{d})")

02810: 完美立方 ​

02810: 完美立方