Chương trình đếm số cặp phân số có tổng bằng 1 trong Python

Mô tả bài toán

Cho danh sách các phân số, mỗi phân số là cặp [tử, mẫu] biểu diễn giá trị tử/mẫu. Tìm số cặp phân số (không phân biệt thứ tự) có tổng bằng 1.

Ví dụ: fractions = [[2,7],[3,12],[4,14],[5,7],[3,4],[1,4]] → đầu ra 4 (các cặp: 2/7+5/7, 3/12+3/4, 3/4+1/4, 4/14+5/7).

Giải thuật

1. Khởi tạo từ điển d đếm tần suất các phân số đã rút gọn.
2. Khởi tạo ans = 0.
3. Duyệt qua từng phân số [x, y]:
   • Rút gọn: g = gcd(x, y), x //= g, y //= g.
   • Phân số bổ sung để tổng = 1 là (y - x, y).
   • Nếu cặp bổ sung đã có trong d: ans += d[(y-x, y)].
   • Tăng số lần xuất hiện của (x, y) trong d.
4. Trả về ans.

Ví dụ mã Python

import math

class Solution:
    def solve(self, fractions):
        d = {}
        ans = 0
        for i in fractions:
            x = i[0]
            y = i[1]
            g = math.gcd(x, y)
            x //= g
            y //= g
            temp_x = y - x
            temp_y = y
            if (temp_x, temp_y) in d:
                ans += d[(temp_x, temp_y)]
            d[(x, y)] = d.get((x, y), 0) + 1
        return ans

ob = Solution()
fractions = [[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]]
print(ob.solve(fractions))

Đầu vào

[[2, 7],[3, 12],[4, 14],[5, 7],[3, 4],[1, 4]]

Đầu ra

4