একটি ম্যাট্রিক্সে ক্রমাগত উপাদানের সংখ্যা খুঁজে বের করার প্রোগ্রাম যার gcd পাইথনে 1 এর থেকে বেশি

ধরুন আমাদের একটি ম্যাট্রিক্স দেওয়া হয়েছে যাতে n সারি এবং m কলাম রয়েছে। আমাদের ম্যাট্রিক্সের সর্বাধিক সংখ্যক ক্রমাগত উপাদানগুলি খুঁজে বের করতে হবে যেখানে উপাদানগুলির gcd 1-এর চেয়ে বেশি। ধারাবাহিক উপাদানগুলি ম্যাট্রিক্সে অনুভূমিকভাবে বা উল্লম্বভাবে থাকতে পারে।

সুতরাং, যদি ইনপুট মত হয়

এবং m =4, n =3; তাহলে আউটপুট হবে 3.

প্রদত্ত ম্যাট্রিক্সের চতুর্থ কলামটি হল 12, 6, 10৷ এই কলামের উপাদানগুলির gcd হল 2৷ তিনটি উপাদান থাকায় উত্তরটি হল 3৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• mat :=m x n x n মাত্রার একটি নতুন 3d তালিকা
• res :=0
  • আমি 0 থেকে n রেঞ্জের জন্য, কর
    i থেকে n রেঞ্জে j-এর জন্য
    • করুন
      • gcd_temp :=0
      • x :=0
      0 থেকে m রেঞ্জে k-এর জন্য
      • করুন
        • যদি i j এর মত হয়, তাহলে
          • mat[i, j, k] :=input_list[i, k]
        • অন্যথায়,
          • mat[i, j, k] =উপাদানগুলির gcd(mat[i, j-1, k], input_list[j, k])
        • gcd_temp =উপাদানগুলির gcd (gcd_temp, mat[i, j, k])
        • যদি gcd_temp> 1 হয়, তাহলে
          • x :=x + j - i + 1
        • অন্যথায়,
          • res :=res এর সর্বোচ্চ, x
          • যদি mat[i, j, k]> 1 হয়, তাহলে
            • gcd_temp :=ম্যাট[i, j, k]
            • x :=j - i + 1
  • res :=res এর সর্বোচ্চ, x
• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

from math import gcd
def solve(n, m, input_list):
   mat = [[[0] *m] *n] *n
   res = 0
   for i in range(n):
      for j in range(i, n):
         gcd_temp = 0
         x = 0
         for k in range(m):
            if i == j:
               mat[i][j][k] = input_list[i][k]
            else:
               mat[i][j][k] = gcd(mat[i][j-1][k], input_list[j][k])
gcd_temp = gcd(gcd_temp, mat[i][j][k])
if gcd_temp > 1:
x += j - i + 1
else:
res = max(res,x)
if mat[i][j][k] > 1:
gcd_temp = mat[i][j][k]
x = j - i + 1
res = max(res,x)
return res
print(solve(3, 4, [[3, 7, 9, 12], [5, 9, 4, 6], [7, 8, 5, 10]]))

ইনপুট

3, 4, [[3, 7, 9, 12], [5, 9, 4, 6], [7, 8, 5, 10]]

আউটপুট

3