Chương trình đếm cặp số tự nhiên có tổng chia hết cho k trong Python

Cho n, k. Xét mảng A = [1..n]. Đếm cặp (i, j) với i < j và (A[i]+A[j]) % k == 0.

Thuật toán

• Đếm tần suất mỗi phần dư modulo k: m = n//k, r = n%k. Phần dư 0..k-1 xuất hiện m lần, dư 1..r thêm 1 lần.
• Cặp (i, k-i) cho tổng chia hết k. Đặc biệt dư 0 và dư k/2 (nếu k chẵn) tự cặp với mình.
• Tổng cặp = sum(freq[i] * freq[k-i]) / 2.

Ví dụ

def solve(n, k):
    m = n // k
    r = n % k
    b = {i: m for i in range(k)}
    for i in range(m*k + 1, n + 1):
        b[i % k] += 1
    c = 0
    for i in range(k):
        i1 = i
        i2 = (k - i) % k
        if i1 == i2:
            c += b[i] * (b[i] - 1)
        else:
            c += b[i1] * b[i2]
    return c // 2

print(solve(10, 4))  # Output: 10

Giải thích

n=10, k=4: 10 cặp [(1,3),(1,7),(2,6),(2,10),(3,5),(3,9),(4,8),(5,7),(6,10),(7,9)].