Chương trình tìm hệ số của phương trình tuyến tính chỉ có một nghiệm trong Python

Giả sử chúng ta có một giá trị n, chúng ta phải tìm số cặp (a, b) [a

Vì vậy, nếu đầu vào là n =4, thì đầu ra sẽ là 2 vì các cặp hợp lệ là (1, 2) và (1, 3).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm divisors_gen (). Điều này sẽ mất n
• divs:=một danh sách các danh sách có kích thước n + 1. Và mỗi danh sách bên trong có 1
• divs [0]:=danh sách chỉ có một phần tử 0
• đối với tôi trong phạm vi từ 2 đến n, thực hiện
  • đối với j trong phạm vi từ 1 đến tầng của (n / i) + 1, thực hiện
    • chèn i vào cuối danh sách tại chỉ mục [i * j]
• trả về div nhưng đảo ngược tất cả danh sách nội bộ
• Từ phương pháp chính, hãy thực hiện như sau -
• kết quả:=0
• d_cache:=divisors_gen (n + 1)
• đối với một trong phạm vi từ 1 đến n - 1, hãy thực hiện
  • i:=1
  • s:=một tập hợp mới
  • while a * i
  • b:=n - a * i
  • đối với mỗi d trong d_cache [b], thực hiện
    • nếu d> a, thì
      • if d not in s, then
        • kết quả:=result + 1
    • nếu không,
      • ra khỏi vòng lặp
    • chèn d vào tập hợp s
  • i:=i + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def divisors_gen(n):
   divs = [[1] for x in range(0, n + 1)]
   divs[0] = [0]
   for i in range(2, n + 1):
      for j in range(1, n // i + 1):
         divs[i * j].append(i)
   return [i[::-1] for i in divs]

def solve(n):
   result = 0
   d_cache = divisors_gen(n+1)

   for a in range(1, n):
      i = 1
      s = set([])
      while a*i < n:
         b = n - a*i
         for d in d_cache[b]:
            if d > a:
               if d not in s:
                  result += 1
            else:
               break
            s.add(d)
         i += 1
   return result

n = 4
print(solve(n))

Đầu vào

4

Đầu ra

2