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

Cho số n, tìm số cặp (a, b) với a < b sao cho phương trình a*x + b*y = n có ít nhất một nghiệm.

Thuật toán

• Tạo mảng divs chứa ước số của mọi số ≤ n+1.
• Duyệt a từ 1 đến n-1, với mỗi a duyệt i sao cho a*i < n.
• Tính b = n - a*i, kiểm tra ước số d của b thỏa d > a và chưa đếm.
• Đếm số cặp hợp lệ.

Ví dụ

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))  # Output: 2

Giải thích

Với n=4, các cặp hợp lệ: (1,2) và (1,3).