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

สมมติว่าเรามีจำนวน n และอีกค่าหนึ่ง k พิจารณาว่าเรามีอาร์เรย์ A ที่มีจำนวนธรรมชาติ N ตัวแรก เราจะต้องหาจำนวนคู่ขององค์ประกอบ A[i] และ A[j] จาก A เท่ากับว่า i

ดังนั้น ถ้าอินพุตเป็นเหมือน n =10 k =4 ผลลัพธ์จะเป็น 10 เพราะมี 10 คู่ที่ผลรวมหารด้วย 4 ลงตัว [(1,3), (1,7), (2,6) , (2,10), (3,5), (3,9), (4,8) (5,7), (6,10), (7,9)]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

m :=ชั้นของ (n / k), r :=n mod k
b :=แผนที่ใหม่
สำหรับฉันในช่วง 0 ถึง k - 1 ทำ
- b[i] :=ม.
สำหรับฉันในช่วง m*k+1 ถึง n ทำ
- j :=ฉัน mod k
- b[j] :=b[j] + 1
ค :=0
สำหรับฉันในช่วง 0 ถึง k ทำ
- i1 :=ฉัน
- i2 :=(k - i) mod k
- ถ้า i1 เหมือนกับ i2 แล้ว
  - c :=c + b[i] *(b[i]-1)
- มิฉะนั้น
  - c :=c + b[i1] *(b[i2])
ชั้นกลับของ 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))

อินพุต

4, 27