हाइपररेक्टेंगल कोशिकाओं में मूल्यों के योग का पता लगाने के लिए पायथन प्रोग्राम

एक हाइपररेक्टेंगल एक आयत है जिसमें k आयाम होते हैं। प्रत्येक आयाम की एक लंबाई होती है जिसे n1, n2, n3,....., nm के रूप में दर्शाया जा सकता है। हाइपररेक्टेंगल की कोशिकाओं को (p,q,r,...) के रूप में संबोधित किया जाता है और इसमें एक मान होता है जो (p,q,r,...) के gcd के बराबर होता है। यहाँ 1 <=p <=n1, 1 <=q <=n1, इत्यादि। हमारा कार्य सभी सेल मानों का योग निर्धारित करना है gcd(p,q,r,...). परिणाम मॉड्यूलो 10^9 + 7 के रूप में लौटाया जाता है। अनुक्रमण 1 से n तक किया जाता है।

इसलिए, यदि इनपुट input_arr =[[2, 2], [5, 5]] जैसा है, तो आउटपुट [5, 37]

होगा।

हमें इनपुट के रूप में दो उदाहरण दिए गए हैं और हमें इन दो दिए गए उदाहरणों का योग निर्धारित करना है। प्रत्येक उदाहरण में, हाइपररेक्टेंगल 4x4 2-आयामी आयत हैं, और लंबाई दी गई है। पता (p,q) और gcd(p,q) इस तरह होगा -

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

जीसीडी का योग =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

जीसीडी का योग =5 + 7 + 7 + 9 + 9 =37

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन को परिभाषित करें coeff_find() । इसमें test_instance लगेगा, मैं
- मान :=1
- test_instance में प्रत्येक k के लिए, करें
  - मान :=value * (k / i) का फ्लोट मान
- वापसी मूल्य
मुख्य विधि/कार्य से, निम्न कार्य करें -
आउटपुट:=एक नई सूची
input_arr में प्रत्येक test_instance के लिए, करें
- min_value :=न्यूनतम test_instance
- कुल_मान :=0
- temp_dict :=एक नया नक्शा
- मेरे लिए min_value से 0 की सीमा में, 1 से घटाएं
  - p :=coeff_find(test_instance, i)
  - q:=मैं
  - जबकि q <=min_value, do
    - 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]