হাইপাররেক্ট্যাঙ্গেল কক্ষে মানের সমষ্টি বের করতে পাইথন প্রোগ্রাম

একটি হাইপাররেক্ট্যাঙ্গেল হল একটি আয়তক্ষেত্র যার 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

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, i

  নিতে হবে
  • মান :=1
  • test_instance-এ প্রতিটি k-এর জন্য, করুন
    • মান :=মান * (k / i) এর ফ্লোট মান
  • রিটার্ন মান
• প্রধান পদ্ধতি/ফাংশন থেকে, নিম্নলিখিতগুলি করুন -
• আউটপুট :=একটি নতুন তালিকা
• input_arr-এ প্রতিটি টেস্ট_ইনস্ট্যান্সের জন্য, করুন
  • min_value :=টেস্ট_ইনস্ট্যান্সের সর্বনিম্ন
  • মোট_মান :=0
  • temp_dict :=একটি নতুন মানচিত্র
  • এর জন্য min_value রেঞ্জে 0 থেকে, 1 কমিয়ে
    করুন
    • p :=coeff_find(test_instance, i)
    • q :=i
    • যখন q <=min_value, do
      • q :=q + i
      • যদি temp_dict-এ q থাকে, তাহলে
        • p :=p - temp_dict[q]
    • temp_dict[i] :=p
    • মোট_মান :=মোট_মান + 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]