โปรแกรมหาสัมประสิทธิ์ของสมการเชิงเส้นที่มีคำตอบเพียงคำตอบเดียวใน Python

สมมติว่ามีค่า n เราต้องหาจำนวนคู่ (a, b) [a < b] ที่ทำให้สมการ a*x + b*y = n มีคำตอบอย่างน้อยหนึ่งคำตอบ

เช่น n = 4 ผลลัพธ์คือ 2 เพราะคู่ที่ถูกต้องคือ (1, 2) และ (1, 3)

วิธีแก้ปัญหา

• กำหนดฟังก์ชัน divisors_gen() รับ n
• divs := รายการของรายการขนาด n+1 แต่ละรายการภายในมีค่า 1
• divs[0] := รายการที่มีเพียง 0
• ลูป i จาก 2 ถึง n
  • ลูป j จาก 1 ถึง floor(n / i) + 1
    • เพิ่ม i ลงท้ายรายการที่ index [i * j]
• คืนค่า divs แต่กลับลำดับรายการภายในทั้งหมด
• จาก main method
  • result := 0
  • d_cache := divisors_gen(n+1)
  • ลูป a จาก 1 ถึง n - 1
    • i := 1
    • s := เซ็ตใหม่
    • while a*i < n
      • b := n - a*i
      • สำหรับแต่ละ d ใน d_cache[b]
        • ถ้า d > a
          • ถ้า d ไม่อยู่ใน s
            • result := result + 1
        • มิฉะนั้น ออกจากลูป
        • เพิ่ม d ลงในเซ็ต s
      • i := i + 1
  • คืนค่า result

ตัวอย่างโค้ด

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))

Input

4

Output

2