โปรแกรม Python หาผลรวมของค่าในเซลล์ไฮเปอร์สี่เหลี่ยมผืนผ้า

ไฮเปอร์สี่เหลี่ยมผืนผ้าคือสี่เหลี่ยมที่มีมิติ k แต่ละมิติมีความยาวที่สามารถแสดงเป็น n1, n2, n3,....., nm เซลล์ของไฮเปอร์สี่เหลี่ยมผืนผ้ามีการระบุเป็น (p,q,r,...) และมีค่าที่เทียบเท่ากับ gcd ของ (p,q,r,...) ที่นี่ 1 <=p <=n1, 1 <=q <=n1 เป็นต้น งานของเราคือกำหนดผลรวมของค่าเซลล์ทั้งหมด gcd(p,q,r,...) ผลลัพธ์จะถูกส่งกลับเป็นโมดูโล 10^9 + 7 การทำดัชนีจะทำจาก 1 ถึง n

ดังนั้น หากอินพุตเป็นเหมือน input_arr =[[2, 2], [5, 5]] ผลลัพธ์จะเป็น [5, 37]

มีสองกรณีที่ให้เราเป็นข้อมูลเข้า และเราต้องพิจารณาผลรวมสำหรับทั้งสองกรณีที่กำหนด ในแต่ละกรณี ไฮเปอร์สี่เหลี่ยมผืนผ้าคือสี่เหลี่ยม 2 มิติ 4x4 และกำหนดความยาว ที่อยู่ (p,q) และ gcd(p,q) จะเป็นดังนี้ -

(p,q)   value   gcd(p,q)
(1, 1)  (1, 2)  1 1
(2, 1)  (2, 2)  1 2

ผลรวมของ gcds =1 + 1 + 1 + 2 =5

ในกรณีที่สอง −

(p,q)  value                gcd(p,q) sum(gcd of row i)
(1, 1) (1, 2) (1, 3) (1, 4) (1, 5)   1 1 1 1 1 = 5
(2, 1) (2, 2) (2, 3) (2, 4) (2, 5)   1 2 1 2 1 = 7
(3, 1) (3, 2) (3, 3) (3, 4) (3, 5)   1 1 3 1 1 = 7
(4, 1) (4, 2) (4, 3) (4, 4) (4, 5)   1 2 1 4 1 = 9
(5, 1) (5, 2) (5, 3) (5, 4) (5, 5)   1 1 1 1 5 = 9

ผลรวมของ gcds =5 + 7 + 7 + 9 + 9 =37

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

• กำหนดฟังก์ชัน coeff_find() นี่จะใช้เวลา test_instance ฉัน

  • ค่า :=1
  • สำหรับแต่ละ k ใน test_instance ทำ
    • ค่า :=ค่า * ค่าลอยตัวของ (k / i)
  • คืนค่า
• จากวิธีการ/ฟังก์ชันหลัก ให้ทำดังต่อไปนี้ −
• ผลลัพธ์ :=รายการใหม่
• สำหรับแต่ละ test_instance ใน input_arr ให้ทำ
  • min_value :=ขั้นต่ำของ test_instance
  • total_value :=0
  • temp_dict :=แผนที่ใหม่
  • สำหรับฉันในช่วง min_value ถึง 0, ลดลง 1 ทำ
    • p :=coeff_find(test_instance, i)
    • q :=ฉัน
    • ในขณะที่ q <=min_value ทำ
      • q :=q + i
      • ถ้า q มีอยู่ใน temp_dict แล้ว
        • p :=p - temp_dict[q]
    • temp_dict[i] :=p
    • total_value :=total_value + temp_dict[i]*i
    • เพิ่ม (total_value mod (10^9 + 7)) ที่ส่วนท้ายของเอาต์พุตรายการ
• ผลตอบแทนที่ได้

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def coeff_find(test_instance, i):
   value = 1
   for k in test_instance:
      value *= k // i
   return value
def solve(input_arr):
   output = []
   for test_instance in input_arr:
      min_value = min(test_instance)
      total_value = 0
      temp_dict = {}
      for i in range(min_value, 0, -1):
         p = coeff_find(test_instance, i)
         q = i
         while q <= min_value:
            q += i
            if q in temp_dict:
               p -= temp_dict[q]
         temp_dict[i] = p
         total_value += temp_dict[i]*i
      output.append(total_value % (10**9 + 7))
   return output
print(solve([[2, 2], [5, 5]]))

อินพุต

[[2, 2], [5, 5]]

ผลลัพธ์

[5, 37]