পাইথনে ম্যাট্রিক্সে GCD ১-র চেয়ে বড় হয় এমন সन्नিহিত উপাদানগুলোর সর্বোচ্চ সংখ্যা বের করার প্রোগ্রাম

একটি ম্যাট্রিক্স দেওয়া আছে যার n সারি এবং m কলাম। ম্যাট্রিক্সে এমন সর্বোচ্চ সংখ্যক সন্নিহিত উপাদান বের করতে হবে যাদের GCD ১-র চেয়ে বড়। সন্নিহিত উপাদানগুলো ম্যাট্রিক্সে আড়াঝাড়া বা লম্বা দিকেই থাকতে পারে।

ইনপুট ম্যাট্রিক্স:

ম্যাট্রিক্সের চতুর্থ কলাম: 12, 6, 10। এই কলামের উপাদানগুলোর GCD হল ২। তিনটি উপাদান থাকায় উত্তর ৩।

সমাধানের ধাপসমূহ

• mat := m × n × n আকারের ৩D লিস্ট
• res := 0
  • i = 0 থেকে n পর্যন্ত:
    • j = i থেকে n পর্যন্ত:
      • gcd_temp := 0, x := 0
      • k = 0 থেকে m পর্যন্ত:
        • যদি 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 := max(res, x)
          • যদি mat[i][j][k] > 1 হয়, তবে gcd_temp := mat[i][j][k], x := j - i + 1
  • res := max(res, x)
• res ফেরত দিন

উদাহরণ

from math import gcd

def solve(n, m, input_list):
    mat = [[[0] * m for _ in range(n)] for _ in range(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