Chương trình Python đếm số cách biểu diễn số x dưới dạng tổng lũy thừa n của các số tự nhiên khác nhau

Cho hai số nguyên x và n. Tìm số cách phân tích x thành tổng của các lũy thừa bậc n của các số tự nhiên khác nhau (mỗi số chỉ dùng tối đa 1 lần).

Ví dụ: x = 100, n = 2 → 3 cách: 10², 6² + 8², 1² + 3² + 4² + 5² + 7².

Thuật toán đệ quy quay lui (Backtracking)

• Hàm solve(x, n, cn=1, cs=0):
  • cn: số tự nhiên hiện tại đang xét (bắt đầu từ 1).
  • cs: tổng hiện tại.
  • Tính p = cn^n.
  • Vòng lặp while p + cs < x: đệ quy thử thêm cn vào tổng.
  • Nếu p + cs == x, tìm thấy 1 cách hợp lệ.

Ví dụ mã nguồn

from math import pow

def solve(x, n, cn=1, cs=0):
    ans = 0
    p = pow(cn, n)
    while p + cs < x:
        ans += solve(x, n, cn + 1, p + cs)
        cn += 1
        p = pow(cn, n)
    if p + cs == x:
        ans += 1
    return ans

x = 100
n = 2
print(solve(x, n))  # 3

Đầu vào / Đầu ra

Input:  100, 2
Output: 3