एक हाइपररेक्टेंगल एक आयत है जिसमें k आयाम होते हैं। प्रत्येक आयाम की एक लंबाई होती है जिसे n1, n2, n3, ..., nm के रूप में दर्शाया जा सकता है। हाइपररेक्टेंगल के सेल्स को (p,q,r,...) के रूप में संबोधित किया जाता है और इसमें एक मान होता है जो (p,q,r,...) के gcd के बराबर होता है। यहां 1 <= p <= n1, 1 <= q <= n2, और इसी तरह। हमारा कार्य 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
gcd का योग = 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
gcd का योग = 5 + 7 + 7 + 9 + 9 = 37
हल करने के चरण
- coeff_find() फंक्शन परिभाषित करें जो test_instance, i लेता है
- मुख्य मेथड/फंक्शन से:
- output := नई सूची
- input_arr में प्रत्येक test_instance के लिए:
- min_value := test_instance का न्यूनतम
- total_value := 0
- temp_dict := नया मैप
- i को min_value से 0 तक, 1 से घटाते हुए:
- p := coeff_find(test_instance, i)
- q := i
- जब 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
- output के अंत में (total_value mod (10^9 + 7)) जोड़ें
- output वापस करें
उदाहरण
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]
