โปรแกรมหาจำนวนคู่จาก N จำนวนธรรมชาตาที่ผลรวมหาร k ลงตัวใน Python

กำหนด n และ k พิจารณา array A ที่มีจำนวนธรรมชาติ N ตัวแรก หาจำนวนคู่ A[i] และ A[j] จาก A ที่ i < j และผลรวมหาร k ลงตัว

เช่น n = 10, k = 4 ผลลัพธ์คือ 10 เพราะมี 10 คู่: [(1,3), (1,7), (2,6), (2,10), (3,5), (3,9), (4,8), (5,7), (6,10), (7,9)]

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

• m := floor(n / k), r := n mod k
• b := map ใหม่
• ลูป i จาก 0 ถึง k-1: b[i] := m
• ลูป i จาก m*k+1 ถึง n: j := i mod k; b[j] := b[j] + 1
• c := 0
• ลูป i จาก 0 ถึง k
  • i1 := i
  • i2 := (k - i) mod k
  • ถ้า i1 == i2: c := c + b[i]*(b[i]-1)
  • มิฉะนั้น: c := c + b[i1]*b[i2]
• คืนค่า floor(c/2)

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

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

n = 10
k = 4
print(solve(n, k))

Input

4, 27

Output

10